6.852 course schedule

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