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.
- 2008-01-14
What the course is about. The TheoryOfDistributedComputing. Basics of MessagePassing models. Example: TwoGenerals. Readings: Chapter 1.
- 2008-01-16
More on MessagePassing models: time and message complexity. Flooding and applications. Readings: §2.1, §2.3.
- 2008-01-18
No lecture. (Out of town.)
- 2008-01-23
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.
- 2008-01-25
LeaderElection: Symmetry breaking; the LCR and HS algorithms; simulating a bidirectional ring in a unidirectional ring. Readings: Chapter 3.
- 2008-01-28
More LeaderElection: Lower bound on message complexity; cheating by exploiting synchrony; randomized algorithms; uniformity vs non-uniformity.
- 2008-01-30
AsynchronousSharedMemory (and some foreshadowing of MutualExclusion). Readings: §4.1.
- 2008-02-01
MutualExclusion: requirements and strong-primitive algorithms. Readings: §§4.2, 4.3.1, and 4.3.2.
- 2008-02-04
MutualExclusion: algorithms using registers only; lower bound on memory. Readings: §§4.4.2–4.4.4.
- 2008-02-06
SynchronousAgreement with crash failures; start of lower bound for same (from IndistinguishabilityProofs). Readings: §5.1.
- 2008-02-08
Lower bound for agreement with crash failures; lower bounds for ByzantineAgreement. Readings: §5.2.
- 2008-02-11
ByzantineAgreement protocols.
- 2008-02-13
The FischerLynchPaterson impossibility result. Readings: §5.3.
- 2008-02-15
Agreement with strong shared-memory objects and the WaitFreeHierarchy: consensus numbers. Readings: §15.1—15.2.
- 2008-02-18
More WaitFreeHierarchy: consensus numbers for exotic multi-register operations.
- 2008-02-20
Still more WaitFreeHierarchy: the revenge of m-way writes, universality of consensus. Readings: §15.3.
- 2008-02-22
RandomizedConsensus: basic model, reduction to shared coin. Readings: §14.3.
- 2008-02-25
More RandomizedConsensus: building a shared coin using voting; the Attiya-Censor algorithm.
- 2008-02-27
SharedMemoryVsMessagePassing: fault-tolerant simulations of shared memory in a message-passing system.
- 2008-02-29
Paxos, start of FailureDetectors.
- 2008-03-03
FailureDetectors. Readings: Chapter 17.
- 2008-03-05
QuorumSystems: load, capacity, and quorum size.
- 2008-03-07
QuorumSystems: availability and fault-tolerance.
- 2008-03-24
LogicalClocks and causal ordering. Readings: §6.1.
- 2008-03-26
More LogicalClocks: Welch clocks, vector clocks, snapshots, replicated state machines. Readings: §6.2.
- 2008-03-28
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.
- 2008-03-31
Broadcast. Readings: Chapter 8, except we won't talk about §8.3 much. More details on the historical examples of broadcast mentioned toward the end of lecture can be found at Spark-gap transmitter.
- 2008-04-02
AtomicSnapshots using repeated collects. Readings: §10.3.
- 2008-04-04
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.
- 2008-04-07
AtomicSnapshots using lattice agreement: implementing lattice agreement. Readings: Inoue et al., Linear-time snapshot using multi-writer multi-reader registers, WDAG 1994.
- 2008-04-09
AtomicSnapshots using LoadLinkedStoreConditional. Readings: Towards a practical snapshot algorithm, Theoretical Computer Science, 269(1–2):163–201, 2001.
- 2008-04-11
SoftwareTransactionalMemory. Readings: Shavit and Touitou, Software Transactional Memory, PODC 1995.
- 2008-04-14
No lecture. (Car trouble.)
- 2008-04-16
ObstructionFree synchronization: simple examples. Readings: Herlihy et al. Obstruction-free synchronization: Double-ended queues as an example. ICSCD 2003.
- 2008-04-18
ObstructionFree synchronization: contention management. Readings: Fich et al., Obstruction-free algorithms can be practically wait-free, DISC 2005.
- 2008-04-21
ObstructionFree synchronization: contention lower bounds, part 1. Readings: Fich et al. Linear lower bounds on real-world implementations of concurrent objects, FOCS 2005.
- 2008-04-23
ObstructionFree synchronization: contention lower bounds, part 2. Readings: Fich et al. Linear lower bounds on real-world implementations of concurrent objects, FOCS 2005.
- 2008-04-25
- 2008-04-28
PeerToPeer systems.
- Final Exam
The final exam was given 2008-05-08 starting at 9:00am in Becton 102. It was a closed-book, cumulative exam covering all material discussed in the lecture and readings. final-2008.pdf final-2008-solutions.pdf