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. For a roughly chronological list of lecture notes, see ../Notes.
LeaderElection in rings. Readings: Chapter 3.
More MutualExclusion: Peterson's tournament algorithm. Burns-Lynch lower bound on memory using a covering argument. Readings: §§4.4.2–4.4.4.
ByzantineAgreement: problem, 3f+1 lower bound on processes, phase king algorithm. Attempts at exponential information gathering foundered when I forgot that up to |w| instances of val(w,i) might be missing because some of the processes in w are Byzantine and thus failed to send out values; see the notes or AttiyaWelch for the correct proof. Readings: §5.2.
Asynchronous agreement with crash failures: the FischerLynchPaterson impossibility result. Readings: §5.3.
Agreement with strong shared-memory objects and the WaitFreeHierarchy: objects with consensus numbers 1 and 2. Readings: §15.1–15.2.
More WaitFreeHierarchy: objects with consensus number ∞; objects with consensus number m > 2.
Still more WaitFreeHierarchy: consensus objects, universality of consensus. Readings: §15.3.
RandomizedConsensus: ratifiers and conciliators; weak-adversary consensus using probabilistic writes. Readings: see notes.
More RandomizedConsensus: strong-adversary consensus: the Attiya-Censor algorithm and variants. Readings: see notes.
SharedMemoryVsMessagePassing: fault-tolerant simulations of shared memory in a message-passing system. Readings: see notes.
Start of FailureDetectors. Definitions, easy reductions and impossibility results. Readings: Chapter 17.
More FailureDetectors: consensus using S and ⋄S.
QuorumSystems: load, capacity, failure probabilities; mostly just the results in the Naor-Wool paper. Readings: see notes.
Start of LogicalClocks. Readings: §6.1.
Applications of LogicalClocks: snapshots and replicated state machines.
Synchronizers. Readings: Chapter 11.
AtomicSnapshots via repeated collects. Readings: §10.3.
AtomicSnapshots: reduction to lattice agreement.
AtomicSnapshots: implementing lattice agreement.
AtomicSnapshots: Riany et al. single-reader algorithm. Applications of snapshots.
Renaming. Readings: §16.3.
More Renaming. The Moir-Anderson algorithm. Readings: Moir-Anderson paper. For students who hung around after class, please be advised that most of the story I told about Gerolamo Cardano and the solution of cubic equations was not actually true.
AdaptiveCollect (more splitter tricks). Readings: see notes.
ObstructionFreedom: examples of obstruction-free algorithms. Readings: see notes.
More ObstructionFreedom: building wait-free algorithms from obstruction-free algorithms. In lecture, the while T[i] ≠ ∞ loop for the winner in the Fich et al. algorithm should have been a repeat..until T[i] = ∞ loop; this fixes the problem with A[i] not getting incremented.
Still more ObstructionFreedom: lower bounds.
TopologicalMethodsInDistributedComputing: representing distributed systems using simplicial complexes. Readings: Herlihy and Shavit, The topological structure of asynchronous computability, JACM, 1999.
More TopologicalMethodsInDistributedComputing: inputs and outputs, the asynchronous computability theorem, applications.
- Final Exam
The final exam was given Monday, May 10th, 2010, starting at 9:00 am, in AKW 200. It was a closed-book, cumulative exam covering all material discussed in the lecture and readings. Exam and solutions: final-2010.pdf, final-2010-solutions.pdf. Previous exams: final-2008.pdf final-2008-solutions.pdf