CS425/2005/Schedule

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 LynchBook Click on each date for detailed notes (if available). As always, the future is uncertain, so you should take parts of the schedule that haven't happened yet with a grain of salt.

<<MonthCalendar: execution failed [Macro instance has no attribute 'form'] (see also the log)>>	<<MonthCalendar: execution failed [Macro instance has no attribute 'form'] (see also the log)>>
<<MonthCalendar: execution failed [Macro instance has no attribute 'form'] (see also the log)>>	<<MonthCalendar: execution failed [Macro instance has no attribute 'form'] (see also the log)>>
<<MonthCalendar: execution failed [Macro instance has no attribute 'form'] (see also the log)>>

Overview of the course. What the TheoryOfDistributedComputing is. Example: the TwoGenerals problem (bogus version---we'll come back and do it right later). Readings: Chapter 1.

SynchronousMessagePassing and start of LeaderElection. Readings: Chapter 2, Sections 3.1-3.3.

More LeaderElection. Readings: Sections 3.3-3.6 (3.7 if you are interested in Ramsey_theory.)

Algorithms for general synchronous networks, including LeaderElection and DistributedBreadthFirstSearch. Readings: Sections 4.1 and 4.2.

DistributedMinimumSpanningTree: the synchronous GHS algorithm. Readings: Section 4.4.

Failures in synchronous systems and IndistinguishabilityProofs. Impossibility of agreement with lost messages and lower bounds on rounds with crash failures. Readings: Sections 5.1, 6.1, and 6.7.

RandomizedCoordinatedAttack. Readings: Section 5.2.

RandomizedCoordinatedAttack lower bound. Knowledge and CommonKnowledge.

SynchronousAgreement algorithms. Readings: 6.1-6.2.

ByzantineAgreement. Readings: 6.3-6.4.

ByzantineAgreement variants. Readings: 6.5-6.6.

IOAutomata. Readings: Chapter 8.

More IOAutomata: fairness, products of trace properties, simulation arguments.

AsynchronousMessagePassing. Readings: Chapter 14.

Asynchronous LeaderElection. Readings: §15.1.

More asynchronous LeaderElection: randomized LCR, Peterson's algorithm. AsynchronousBroadcast. Readings: §15.1.3, §15.3.

Asynchronous DistributedBreadthFirstSearch. Readings: §15.4.

Synchronizers. Readings: Chapter 16.

The FischerLynchPaterson impossibility result for asynchronous consensus with one crash failure. Readings: Chapter 12 gives the shared-memory version of the proof (originally due to Loui and Abu-Amara, based on the FLP result); we did the message-passing version from the original FLP paper, which can be found here.

AsynchronousSharedMemory. Readings: Chapter 9. (See also Chapter 13 for definitions of atomic objects, since some of this will leak into our model.)

MutualExclusion: problem statement and some algorithms. Readings: Chapter 10.

More MutualExclusion: lower bounds. Readings: §10.8.

SharedMemoryVsMessagePassing: simulations. Readings: Chapter 17.

Simulating shared-memory objects. Trivial failure-free method using locking. Wait-free approach using AtomicSnapshots of shared memory. Building multiwriter registers from single-writer registers. Readings: Chapter 13.

Simulating atomic objects other than registers. The WaitFreeHierarchy: levels 1, 2, and ∞. Readings: Herlihy, Wait-free synchronization, TOPLAS 13(1):124-149, but see also Jayanti, Robust wait-free hierarchies, JACM 44(4):592-614, 1997 and Ruppert, Determining consensus numbers, SICOMP 30(4):1156-1168, 2000.

More WaitFreeHierarchy: intermediate levels, universality of consensus. Readings: Herlihy, Wait-free synchronization, TOPLAS 13(1):124-149.

RandomizedConsensus. Readings: Aspnes, Randomized protocols for asynchronous consensus, Distributed Computing 16(2-3):165-175, 2003.

SoftwareTransactionalMemory. Readings: Shavit and Touitou, Software transactional memory, PODC 1995, Harris et al, A practical multi-word compare-and-swap, DISC 2002.

The Paxos consensus protocol. Readings: Lamport, Paxos made simple, SIGACT News 32(4):18-25, 2001. See also http://research.microsoft.com/users/lamport/pubs/pubs.html#lamport-paxos for the backstory and a link to the original paper.

FailureDetectors: classification, consensus using S. Readings: Chandra and Toueg, Unreliable failure detectors for reliable distributed systems, JACM 43(2):225–267, 1996.

More FailureDetectors: impossibility of consensus for f ≥ n/2 using ⋄P, consensus for f < n/2 using ⋄S, relations between detector classes. Readings: Chandra and Toueg, Unreliable failure detectors for reliable distributed systems, JACM 43(2):225–267, 1996.

LogicalTime and ConsistentSnapshot protocols. Readings: Chapter 18, §19.2.2.

Group membership services. Readings: Birman and Joseph, Reliable communication in presence of failures. ACM TOCS 5(1):47–76, 1987.

QuorumSystems. Readings: see QuorumSystems page.

Probabilistic QuorumSystems. Readings: see notes.

PeerToPeer systems. Readings: see notes.

CANCELLED

FiniteStateProtocols.

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