6.852/18.437  Distributed Algorithms

Distributed Algorithms are algorithms designed to run on multiple processors, without tight centralized control. In general, they are harder to design, and harder to understand, then single-processor sequential algorithms. Distributed algorithms are used in many practical systems, ranging from large computer networks to multiprocessor shared-memory systems. They also have a rich theory, which forms the subject matter for this course.

Theoretical results about distributed algorithms appear in research conferences such as PODC (Principles Of Distributed Computing), DISC (International Symposium on DIStributed Computing), OPODIS (International Conference on Principles of Distributed Systems), and SPAA (ACM Symposium on Parallelism in Algorithms and Architectures). They also appear in general theoretical computer science conferences such as FOCS (Foundations of Computer Science) and STOC (Symposium on Theory of Computing), and in broad conferences involving distributed computing, such as ICDCS (International Conference on Distributed Computing Systems).

What do distributed algorithms researchers do? They (we) define various kinds of distributed computing environments, including shared-memory and network-based environments, and identify problems to be solved in those environments. They design new algorithms for these problems, and analyze the correctness, performance, and fault-tolerance of their algorithms. They also prove lower bounds and other impossibility results, which explain why certain tasks cannot be carried out in certain kinds of distributed settings, or cannot be carried out within certain cost constraints. Researchers typically study problems that arise in practical distributed systems, including problems of communication, data management, resource management, synchronization, and distributed agreement. Sometimes, the results have impact on practical distributed system design.

This year, the course will be taught by Prof. Lynch, with some help from Dr. Victor Luchangco, a member of the Scalable Systems research group at Sun Microsystems Research. The ``core'' of the material will consist of basic distributed algorithms and impossibility results, as covered in Lynch's book ``Distributed Algorithms''. This will be supplemented by some updated material on topics such as self-stabilization, wait-free computability, and failure detectors, and some new material on scalable shared-memory concurrent programming.

6.852 is a graduate-level course that is intended to do two things: provide an introduction to the most important basic results in the area of distributed algorithms, and prepare interested students to begin independent research or take a more advanced course in distributed algorithms. Usually, the students who take the course are a mixture of PhD students and MEng students. Since the course is run at a PhD level, most MEng students should find it challenging.

To take 6.852, you should have:

• ``Mathematical maturity''. In particular, you should be very good at reading and writing mathematical proofs.

• General knowledge about some distributed systems. For instance, MIT's undergraduate course 6.033, Computer Systems Engineering, would be good background.

• Experience with sequential algorithms and their analysis. MIT's undergrad course 6.046 is sufficient.

• (Desirable, but not essential) Experience with formal models of computation. MIT's course 6.045 or 6.840 would be fine for this.