| Date |
Topic |
Readings |
Handouts |
Notes |
| 09.08.04 |
Introduction and course
overview:
synchronous message passing model, Consensus problem and its variants Early-stopping consensus algorithms |
A survey by Michael
Fischer Lamport and Fischer Dolev, Reischuk and Strong N. Lynch. Distributed Algorithms.
Chapter 6 for consensus algorithms for stopping failures. |
Homework assignment 1. Due September 15, at class. Reading list |
Lecture1
(.tex)
(.ps) |
| 09.15.04 |
Number of rounds for Consensus: Gregory Chockler |
Aguilera and Toueg Keidar and Rajsbaum Moses and Rajsbaum's original paper on layering. Introduces the techique used to obtain the f+2 bound A shorter conference (PODC'98) version of the same paper |
Homework assignment 2. Due September 22, at class. | Lecture 2 slides (2 per page) (.pdf) |
| 09.22.04 |
Synchronous
Byzantine Consensus:
A solution using echo broadcast |
N. Lynch, Distributed Algorithms, Sections 6.3.4, 6.4 Srikanth and Toueg H. Attiya and J. Welch, Distributed Computing, 1st Edition, Section 12.3 |
Homework assignment 3. Due September 29, at class. | Lecture 3 slides (2 per page) (.pdf) |
| 09.29.04 |
Asynchronous shared memory
and impossiility of wait-free Consensus:
|
Attiya and Welch. Distributed Computing. Section 4.1 and 5.3.1 M. Herlihy, Wait-Free Synchronization: Discusses the power of shared variables in terms of their ability to implement wait-free Consensus |
NA | Lecture 4 slides (2 per page) (.pdf) |
| 10.06.04 |
Impossibility of
1-resilient Consensus:
Message passing: Reduction from 1-resilient message-passing. |
Attiya and Welch. Distributed Computing. Sections 5.3.2 and 5.3.3 | Homework assignment 4. Due October 13, at class. | Lecture 5 slides (2 per page) (.pdf) |
Shared Objects
|
M. Herlihy,
Wait-Free Synchronization
L. Lamport, On Interprocess Communication. Part I and II: Defines different types of R/W registers (safe, regular and atomic) and shows their implementations in a rigorous mathemtical framework |
NA | Lecture 6 slides (2 per page) (.pdf) | |
| 10.13.04 |
Circumventing Impossibility:
Partial synchrony
|
Dolev, Dwork and Stockmeyer Dwork, Lynch, Stockmeyer |
NA | Lecture 7 slides (2 per page) (.pdf) |
| 10.20.04 |
Circumventing
impossibility: Failure detectors Gregory Chockler |
Chandra and Toueg | NA | Lecture 8 slides (2 per page) (.pdf) |
| 10.27.04 |
The weakest failure detector for
Consensus: Gregory Chockler |
Chandra, Hadzilacod and Toueg Gartner, Guerraoui and Kouznetsov: an informal overview of the CHT proof. A good starting point. |
NA | Lecture 9 slides (2 per page) (.pdf) |
| 11.03.04 |
CHT proof continued...: Gregory Chockler |
Ditto | NA | Lecture 9 slides (2 per page) (.pdf) |
| 11.10.04 |
The Paxos Algorithm: Murat Demirbas |
Leslie Lamport, Paxos Made Simple Leslie Lamport, The Part-Time Parliament |
NA | Presentation slides: PDF |
| 11.17.04 |
Constructing reliable objects from unreliable storage: Velin Tzanov |
Abraham, Chockler, Malkhi, Keidar | NA | Talk slides (1 per page) (.pdf) |
| 11.24.04 |
Wait-free
vs. f-fault-tolerant data objects: Paul Attie Rui Fan |
Attie, Guerraoui, Kouznetsov, Lynch, Rajsbaum Chandra, Hadzilacos, Jayanti, Toueg | NA | Presentation slides (1 per page) (.pdf) |
| 12.01.04 |
Shared memory vs.
message passing:
|
Disk Paxos,
Lo and Hadzilacos,
Guerraoui et al Abraham, Chockler, Keidar, Malkhi |
NA |
Presentation slides (1 per page): Calvin: (.pdf) Shinya: (.pdf) |
| 12.08.04 |
The Quorum Deployment Problem: Seth Gilbert
|
Gilbert and Malewicz | NA | Talk Slides: Postscript |
|
Conclusions and open problems: Gregory Chockler |
NA | NA | NA |