Lecture
|
Topic
|
|
|
1 (Sept. 8) |
Course overview. Synchronous networks. Leader election in
synchronous ring networks. |
Ch.1, 2 (skim). Ch.3, sections 3.1-3.4. |
|
2 (Sept. 13) |
Basic computational tasks in synchronous networks: Leader
election. Breadth-first search. Shortest paths. Broadcast and convergecast. |
Ch.3, sections 3.1-3.6. |
|
3 (Sept. 15) |
Breadth-first search. Shortest paths. Broadcast and
convergecast. Spanning trees. Minimum spanning trees. |
Ch.4, sections 4.1-4.4. |
|
4 (Sept. 20) |
Fault-tolerant consensus. Link failures: The Two Generals
problem. Process failures (stopping, Byzantine). Algorithms for agreement
with stopping failures. |
Ch.5, section 5.1. Ch.6, sections 6.1, 6.2. |
|
5 (Sept. 22) |
Exponential information gathering. Algorithms for
agreement with Byzantine failures. |
Ch.6, sections 6.2, 6.7. |
|
6 (Sept. 27) |
Number-of-processes lower bounds for Byzantine agreement. Weak
Byzantine agreement. Time bounds for consensus problems. |
Ch.6, sections 6.3-6.6. Aguilera, Toueg paper in handout 3. |
|
7 (Sept. 29) |
Other kinds of consensus problems: $k$-agreement.
Approximate agreement. Distributed commit. |
Ch.7, sections 7.1-7.3 (skip 7.3.4). |
|
8 (Oct. 4) |
Asynchronous distributed computing. Formal modeling of
asynchronous systems using I/O automata. |
Ch.7, section 7.3. Ch.8. |
|
9 (Oct. 6) |
Proof methods. Non-fault-tolerant algorithms for asynchronous
networks. Leader election, breadth-first search, shortest paths, broadcast
and convergecast. |
Ch.8, sections 8.2-8.5. Ch.14, 15. |
|
(Oct. 11) |
Holiday:
Columbus Day |
|
|
10 (Oct. 13) |
Non-fault-tolerant algorithms for asynchronous networks.
Leader election, breadth-first search, shortest paths, broadcast and
convergecast. |
Ch.15, sections 15.3-15.4. |
|
11 (Oct. 18) |
Spanning trees. Gallager et al. Minimim Spanning Tree
algorithm. |
Ch.15, sections 15.4, 15.5. |
|
12 (Oct. 20) |
Synchronizers. |
Ch.16. |
|
13 (Oct. 25) |
Synchronizer applications. Time, clocks, and the ordering
of events. Vector timestamps. |
Ch.16, section 16.6. Ch.18. Lamport’s “Time, Clocks, …” paper. |
|
14 (Oct. 27) |
State-machine simulation. Synchronous vs. asynchronous
distributed systems Stable property detection. Distributed termination.
Global snapshots. Deadlock detection. Asynchronous shared-memory systems. |
Mattern paper. Ch.19. |
|
15 (Nov. 1) |
Mutual exclusion. Mutual exclusion algorithms. |
Ch.9. Ch.10 (sections 10.1-10.5). |
|
16 (Nov. 3) |
Mutual exclusion algorithms. |
Ch.10 (10.5-10.8). |
|
17 (Nov. 8) |
Bounds on shared-memory for mutual exclusion. |
Ch.10, (10.8-10.9). Ch.11 (skim). |
|
18 (Nov. 10) |
Impossibility of consensus in asynchronous, fault-prone,
shared-memory systems. |
Ch.12. Ch.13, section 13.1. |
|
19 (Nov. 15) |
Atomic objects. Atomic snapshot algorithms. |
Ch.13. |
|
20 (Nov. 17) |
Atomic read/write register algorithms. Wait-free
computability. The wait-free consensus hierarchy. |
Ch.13. Herlihy’s “Wait-free Synchronization” paper. |
|
21 (Nov. 22) |
The wait-free consensus hierarchy. |
Herlihy’s “Wait-free Synchronization” paper. Jayanti papers (skim). |
|
(Nov. 24) |
Holiday:
Thanksgiving |
|
|
22 (Nov. 29) |
Wait-free vs. $f$-fault-tolerant atomic objects. |
Borrowsky, Gafni, Lynch, Rajsbaum paper. |
|
23 (Dec. 1) |
Asynchronous network model vs. asynchronous shared-memory model.
Impossibility of consensus in asynchronous networks. Failure detectors and
consensus. |
Ch.17, 21. |
|
24 (Dec. 6) |
Paxos consensus algorithm. Reliable communication using
unreliable channels. |
Lamport’s “Part Time Parliament” paper. Ch.22. |
|
25 (Dec. 8) |
Reliable communication using unreliable channels.
Self-stabilizing algorithms. |
Ch.22. Dijkstra’s self-stabilization paper. Dolev’s self-stabilization book, chapter 2. |
|
26 (Dec. 13) |
Atomic memory algorithms for dynamic networks. Rambo. |
Rambo papers, by Lynch and Shvartsman; and Gilbert, Lynch, and Shvartsman |