This course is no longer offered
22903 Distributed Algorithms
Credits: 4 graduate credits in Computer Science
Prerequisite: Admission to the graduate program in Computer Science 1
The course is based on a reader edited by Gadi Taubenfeld.
A distributed system is a collection of independent processors that communicate with each other by reading and writing from a shared memory or by sending messages through a communication network. The uses of distributed systems are many and varied. For example, solving a problem using many processors is faster than a sequential solution performed by a single processor; storing data in several places to increase efficiency and reliability; the use of common resources such as printers and disks by several processors; and of course, sending electronic mail.
The course examines various outcomes resulting from recent research into the theoretical basis of distributed systems design. These outcomes include distributed algorithms, upper and lower bounds, and impossibility results. Solutions to various problems will be presented; for example, mutual exclusion, election of a leader in a network, distributed consensus, constructing a minimum-weight spanning tree, deadlock detection, snapshot algorithm, self-stabilizing systems, wait-free synchronization, and more. The materials emphasize outcomes in the context of realistic models assuming crashes characteristic of existing systems.
1Students who have not fulfilled this requirement may, under certain circumstances, enroll in this course.