[FrontPage] [TitleIndex] [WordIndex]

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

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

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

2010-03-03

Applications of LogicalClocks: snapshots and replicated state machines.

2010-03-05

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

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

2010-04-12
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

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

2014-06-17 11:58