Massachusetts Insitute for Technology
6.895 Advanced Distributed Algorithms, Fall Term 2002
Professor Nancy Lynch

Handout 3 - Course Schedule

September:

Class 1: Thursday, Sept. 5, Nancy Lynch
Introduction to the course. Shared memory algorithms: Mutual exclusion.

Papers covered:
Lamport. A Fast Mutual Exclusion Algorithm
Friedberg, Peterson. An Efficient Solution to the Mutual Exclusion Algorithm Using Weak Semaphores.

Class 2: Tuesday, Sept. 10, Nancy Lynch
Shared memory: Renaming. Snapshot and collect.

Papers covered:
Moir, Anderson. Wait-free Algorithms for Fast, Long-Lived Renaming.
Attiya, Fouren. Adaptive and Efficient Algorithms for Lattice Agreement and Renaming.
Attiya, Fouren. Polynomial and Adaptive Long-lived (2k-1)-Renaming
Afek, Stupp, Touitou. Long-lived and Adaptive Collect with Applications

Class 3: Thursday, Sept. 12, Nancy Lynch
Shared memory: Computing with an unknown set of participants. Computing with faulty objects

Papers covered: (tentative)
Merritt, Taubenfeld. Computing with Infinitely Many Processes.
Gafni, Merritt, Taubenfeld. The concurrency hierarchy, and algorithms for unbounded concurrency.
Afek, Greenberg, Merritt, Taubenfeld. Computing with Faulty Shared Objects.
Jayanti, Chandra, Toueg. Fault-tolerant wait-free shared objects.

Class 4: Tuesday, Sept. 17
Client-server computing: Byzantine quorum systems.

Class 5: Thursday, Sept. 19
Client-server computing: Data replication.

Class 6: Tuesday, Sept. 24
Client-server computing: Disk Paxos. Disk Paxos with infinitely many processes.

Class 7: Thursday, Sept. 26
Networks with known participants: Logical time. Clock synchronization.

October:

Class 8: Tuesday, Oct. 1
Networks with known participants: Failure detectors

Class 9: Thursday, Oct. 3
Failure detectors.

Class 10: Tuesday, Oct. 8
Networks with known participants: Fault-tolerant broadcasts.

Class 11: Thursday, Oct. 10
Networks with known participants: Consensus. The Paxos algorithm.

Tuesday, Oct. 15: Columbus Day, Vacation---NO CLASS.

Class 12: Thursday, Oct. 17
Consensus: Early stopping algorithms

Class 13: Tuesday, Oct. 22
Networks with known participants: Data replication.

Class 14: Thursday, Oct. 24
Networks with known participants: Performing work in distributed systems.

Class 15: Tuesday, Oct. 29
Networks with known participants: Self-stabilizing systems.

Class 16: Thursday, Oct. 31
Self-stabilizing systems.

November:

Class 17: Tuesday, Nov. 5
Networks with unknown participants: End-to-end communication and routing. Building communication structures.

Class 18: Thursday, Nov. 7
Group communication

Class 19: Tuesday, Nov. 12
Group communication

Class 20: Thursday, Nov. 14
Peer-to-peer networks: Location services.

Class 21: Tuesday, Nov. 19
Location services, continued

Class 22: Thursday, Nov. 21
Reconfigurable atomic memory: The RAMBO algorithm.

Class 23: Tuesday, Nov. 26
Mobile computing: Topology control.

December:

Class 24: Tuesday, Dec. 3
Mobile computing: Routing and end-to-end communication.

Class 25: Thursday, Dec. 5
Mobile computing: Leader election, mutual exclusion and other problems.

Class 26: Tuesday, Dec. 10

Mobile computing: Coordinated robots.