Lecture |
Topic |
Instructor |
Notes |
| 1 (Sept. 4) | Overview. Synchronous networks. Leader election in synchronous ring networks. | Rodrigo Rodrigues | |
| 2 (Sept. 9) | Basic computational tasks in synchronous networks: Leader election. Breadth-first search. | Nancy Lynch | Lecture 2 |
| 3 (Sept. 11) | Shortest-paths. Minimum spanning trees. | Nancy Lynch | Lecture 3 |
| 4 (Sept. 16) | Depth-first search. Consensus with link failures and process stopping failures. | Nancy Lynch | Lecture 4 |
| 5 (Sept. 18) | Lower bounds for consensus. | Nancy Lynch | Lecture 5 |
| 6 (Sept. 23) | Consensus with Byzantine failures. Number of processor bounds for Byzantine agreement. | Nancy Lynch | Lecture 6 |
| 7 (Sept. 25) | Weak Byzantine agreement. Time bounds for consensus problems. Other kinds of consensus problems: k-agreement. | Nancy Lynch | Lecture 7 |
| 8 (Sept. 30) | Distributed Commit. Asynchronous distributed computing. Formal modeling of asynchronous systems using I/O automata. | Rodrigo Rodrigues | Lecture 8 |
| 9 (Oct. 2) | I/O Automata (cont.) Proof methods. Non-fault-tolerant algorithms for asynchronous networks. Leader-election. | Rodrigo Rodrigues | Lecture 9 |
| 10 (Oct. 7) | Lower bound for leader election. Breadth-first search. Shortest paths, broadcast, convergecast. Minimum spanning trees. | Rodrigo Rodrigues | Lecture 10 |
| 11 (Oct. 9) | Self-stabilization | Shlomi Dolev | Postscript slides, PPT slides. |
| 12 (Oct. 14) | Self-stabilization | Shlomi Dolev | Postscript slides, PPT slides. |
| 13 (Oct. 16) | Minimum spanning trees (cont.) Synchronizers. | Nancy Lynch | Lecture 13 |
| 14 (Oct. 21) | (Cancelled.) | ||
| 15 (Oct. 23) | Synchronizer applications. Synchronous vs. asynchronous distributed systems. Time, clocks, and the ordering of the events. State-machine simulation. Vector Timestamps. | Rodrigo Rodrigues | Lecture 15 |
| 16 (Oct. 28) | Stable property detection. Distributed termination. Global snapshots. Deadlock detection. | Mark Moir | Lecture 16 |
| 17 (Oct. 30) | Introduction to asynchronous shared-memory systems. Mutual exclusion. | Nir Shavit |
Slides
These are NOT for
distribution and should only be used for purposes of this class. Lynch's Notes for Lecture 17 |
| 18 (Nov. 4) | Atomic objects, linearizability. | Nir Shavit |
Slides
Lynch's Notes for Lecture 18 |
| 19 (Nov. 6) | Atomic read/write register algorithms, atomic snapshot algorithms. | Nir Shavit |
Slides
Lynch's Notes for Lecture 19 |
| 20 (Nov. 13) | Impossibility of consensus in asynchronous fault-prone systems (FLP). | Mark Moir |
Slides
Lynch's Notes for Lecture 20 |
| 21 (Nov. 18) | Wait-free consensus hierarchy, universal construction | Victor Luchangco | Slides |
| 22 (Nov. 20) | Pragmatics. Shared Memory vs. Networks | Victor Luchangco | Notes |
| 23 (Nov. 25) | Paxos | Butler Lampson | Slides |
| 24 (Dec. 2) | Reliable communication on unreliable channels. | Roger Khazan | Lecture 24 |
| 25 (Dec. 4) | Timing-based systems. Modeling and verification. | Victor Luchangco | Notes |
| 26 (Dec. 9) | Transactional memory, future directions. | Maurice Herlihy |