Unless otherwise specified, all readings are in AttiyaWelch. As always, the future is uncertain, so you should take parts of the schedule that haven't happened yet with a grain of salt.
No lecture. (Out of town.)
Distributed BFS trees. Readings: DistributedBreadthFirstSearch. You should also read the rest of Chapter 2, even though we didn't cover all of it in lecture.
LeaderElection: Symmetry breaking; the LCR and HS algorithms; simulating a bidirectional ring in a unidirectional ring. Readings: Chapter 3.
More LeaderElection: Lower bound on message complexity; cheating by exploiting synchrony; randomized algorithms; uniformity vs non-uniformity.
MutualExclusion: requirements and strong-primitive algorithms. Readings: §§4.2, 4.3.1, and 4.3.2.
MutualExclusion: algorithms using registers only; lower bound on memory. Readings: §§4.4.2–4.4.4.
Lower bound for agreement with crash failures; lower bounds for ByzantineAgreement. Readings: §5.2.
The FischerLynchPaterson impossibility result. Readings: §5.3.
Agreement with strong shared-memory objects and the WaitFreeHierarchy: consensus numbers. Readings: §15.1—15.2.
More WaitFreeHierarchy: consensus numbers for exotic multi-register operations.
Still more WaitFreeHierarchy: the revenge of m-way writes, universality of consensus. Readings: §15.3.
RandomizedConsensus: basic model, reduction to shared coin. Readings: §14.3.
More RandomizedConsensus: building a shared coin using voting; the Attiya-Censor algorithm.
SharedMemoryVsMessagePassing: fault-tolerant simulations of shared memory in a message-passing system.
FailureDetectors. Readings: Chapter 17.
QuorumSystems: load, capacity, and quorum size.
QuorumSystems: availability and fault-tolerance.
LogicalClocks and causal ordering. Readings: §6.1.
More LogicalClocks: Welch clocks, vector clocks, snapshots, replicated state machines. Readings: §6.2.
Synchronizers; the SessionProblem. Readings: Chapter 11. Correction: the reason my eta looked funny in lecture was that I was really trying to draw a zeta (ζ). See the notes for pointers to the zeta synchronizer for dynamic networks.
AtomicSnapshots using repeated collects. Readings: §10.3.
AtomicSnapshots using lattice agreement: reduction to lattice agreement. Readings: Sections 1–3 of Attiya, Herlihy, and Rachman, Atomic snapshots using lattice agreement:, Distributed Computing 8:121–132, 1995.
AtomicSnapshots using lattice agreement: implementing lattice agreement. Readings: Inoue et al., Linear-time snapshot using multi-writer multi-reader registers, WDAG 1994.
No lecture. (Car trouble.)
ObstructionFree synchronization: simple examples. Readings: Herlihy et al. Obstruction-free synchronization: Double-ended queues as an example. ICSCD 2003.
ObstructionFree synchronization: contention management. Readings: Fich et al., Obstruction-free algorithms can be practically wait-free, DISC 2005.
ObstructionFree synchronization: contention lower bounds, part 1. Readings: Fich et al. Linear lower bounds on real-world implementations of concurrent objects, FOCS 2005.
ObstructionFree synchronization: contention lower bounds, part 2. Readings: Fich et al. Linear lower bounds on real-world implementations of concurrent objects, FOCS 2005.