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.
- 2010-01-11
What the course is about. The TheoryOfDistributedComputing. Basics of MessagePassing models. Example: TwoGenerals. Readings: Chapter 1.
- 2010-01-13
Asynchronous MessagePassing: algorithms and complexity measures. Flooding. Readings: Chapter 2.
- 2010-01-15
More MessagePassing algorithms: ConvergeCast and DistributedBreadthFirstSearch.
- 2010-01-20
LeaderElection in rings. Readings: Chapter 3.
- 2010-01-22
AsynchronousSharedMemory and MutualExclusion; mutual exclusion with strong primitives. Readings: §§4.1–4.2, 4.3.1, and 4.3.2.
- 2010-01-25
More MutualExclusion: Peterson's tournament algorithm. Burns-Lynch lower bound on memory using a covering argument. Readings: §§4.4.2–4.4.4.
- 2010-01-27
SynchronousAgreement with crash failures: model, solution using flooding, f+1 lower bound on number of rounds (from IndistinguishabilityProofs). Readings: §5.1.
- 2010-01-29
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.
- 2010-02-01
Asynchronous agreement with crash failures: the FischerLynchPaterson impossibility result. Readings: §5.3.
- 2010-02-03
Agreement with strong shared-memory objects and the WaitFreeHierarchy: objects with consensus numbers 1 and 2. Readings: §15.1–15.2.
- 2010-02-05
More WaitFreeHierarchy: objects with consensus number ∞; objects with consensus number m > 2.
- 2010-02-08
Still more WaitFreeHierarchy: consensus objects, universality of consensus. Readings: §15.3.
- 2010-02-10
RandomizedConsensus: ratifiers and conciliators; weak-adversary consensus using probabilistic writes. Readings: see notes.
- 2010-02-12
More RandomizedConsensus: strong-adversary consensus: the Attiya-Censor algorithm and variants. Readings: see notes.
- 2010-02-15
SharedMemoryVsMessagePassing: fault-tolerant simulations of shared memory in a message-passing system. Readings: see notes.
- 2010-02-17
- 2010-02-19
Start of FailureDetectors. Definitions, easy reductions and impossibility results. Readings: Chapter 17.
- 2010-02-22
More FailureDetectors: consensus using S and ⋄S.
- 2010-02-24
QuorumSystems: load, capacity, failure probabilities; mostly just the results in the Naor-Wool paper. Readings: see notes.
- 2010-02-26
PeerToPeer systems and the SybilAttack. Readings: sybil-attack.pdf, sybilguard.pdf.
- 2010-03-01
Start of LogicalClocks. Readings: §6.1.
- 2010-03-03
Applications of LogicalClocks: snapshots and replicated state machines.
- 2010-03-05
Synchronizers. Readings: Chapter 11.
- 2010-03-22
AtomicSnapshots via repeated collects. Readings: §10.3.
- 2010-03-24
AtomicSnapshots: reduction to lattice agreement.
- 2010-03-26
AtomicSnapshots: implementing lattice agreement.
- 2010-03-29
AtomicSnapshots: Riany et al. single-reader algorithm. Applications of snapshots.
- 2010-03-31
Lower bounds on shared-memory objects: the JayantiTanToueg bound. Bounded MaxRegisters as an example of evading the bound. Readings: Jayanti, Tan, Toueg paper.
- 2010-04-02
More MaxRegisters: using max registers to build counters. Optimality of the AAC construction. Readings: Aspnes, Attiya, Censor paper.
- 2010-04-05
Renaming. Readings: §16.3.
- 2010-04-07
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.
- 2010-04-09
AdaptiveCollect (more splitter tricks). Readings: see notes.
- 2010-04-12
SoftwareTransactionalMemory. Readings: Shavit and Touitou, Software transactional memory, PODC 1995.
- 2010-04-14
ObstructionFreedom: examples of obstruction-free algorithms. Readings: see notes.
- 2010-04-16
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.
- 2010-04-19
Still more ObstructionFreedom: lower bounds.
- 2010-04-21
TopologicalMethodsInDistributedComputing: representing distributed systems using simplicial complexes. Readings: Herlihy and Shavit, The topological structure of asynchronous computability, JACM, 1999.
- 2010-04-23
More TopologicalMethodsInDistributedComputing: inputs and outputs, the asynchronous computability theorem, applications.
- 2010-04-26
PopulationProtocols. Readings: Aspnes and Ruppert, An introduction to population protocols, 2009.
- 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