• CS425
• Schedule

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

RadioNetworks.

2008-04-28

PeerToPeer systems.