Consensus and Byzantine Fault Tolerance
Slides:
Assigned Readings:
- Monday, 3/8
- Respond on Blackboard Discussion: Lamport, L., Shostak, R., and Pease, M. 1982. The Byzantine Generals Problem. ACM Trans. Program. Lang. Syst. 4, 3 (Jul. 1982), 382-401.
- Wednesday, 3/10
- Respond on Blackboard Discussion: Lamport, L. 1998. The part-time parliament. ACM Trans. Comput. Syst. 16, 2 (May. 1998), 133-169.
- "Simplified" version of prior paper: Paxos Made Simple by Leslie Lamport, in Rajsbaum, S. 2001. ACM SIGACT news distributed computing column 5. SIGACT News 32, 4 (Dec. 2001), 34-58. --- From Leslie, "At the PODC 2001 conference, I got tired of everyone saying how difficult it was to understand the Paxos algorithm, published in [The part-time parliament]. Although people got so hung up in the pseudo-Greek names that they found the paper hard to understand, the algorithm itself is very simple. So, I cornered a couple of people at the conference and explained the algorithm to them orally, with no paper. When I got home, I wrote down the explanation as a short note, which I later revised based on comments from Fred Schneider and Butler Lampson. The current version is 13 pages long, and contains no formula more complicated than n1 > n2."
- Monday 3/15 and Wednesday 3/17
- SPRING BREAK! NO CLASS!
- Monday, 3/22
- No Paper Today!
- Wednesday, 3/24
- Respond on Blackboard Discussion: M. Castro, and B. Liskov, "Practical Byzantine Fault Tolerance", Symposium on Operating Systems Design and Implementation (OSDI'99), New Orleans, USA, February 1999
Additional Reading (not assigned):
- Chandra, T. D., Griesemer, R., and Redstone, J. 2007. Paxos made live: an engineering perspective. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing (Portland, Oregon, USA, August 12 - 15, 2007). PODC '07. ACM, New York, NY, 398-407.
- Kirsch, J. and Amir, Y. 2008. Paxos for System Builders: an overview. In Proceedings of the 2nd Workshop on Large-Scale Distributed Systems and Middleware (Yorktown Heights, New York, September 15 - 17, 2008). LADIS '08, vol. 341. ACM, New York, NY, 1-6.
- NSDI 2009 - Making Byzantine Fault Tolerant Systems Tolerate Byzantine Faults Allen Clement, Edmund Wong, Lorenzo Alvisi, and Mike Dahlin, The University of Texas at Austin; Mirco Marchetti, The University of Modena and Reggio Emilia
- Kotla, R., Alvisi, L., Dahlin, M., Clement, A., and Wong, E. 2009. Zyzzyva: Speculative Byzantine fault tolerance. ACM Trans. Comput. Syst. 27, 4 (Dec. 2009), 1-39.
- Aiyer, A. S., Alvisi, L., Clement, A., Dahlin, M., Martin, J., and Porth, C. 2005. BAR fault tolerance for cooperative services. In Proceedings of the Twentieth ACM Symposium on Operating Systems Principles (Brighton, United Kingdom, October 23 - 26, 2005). SOSP '05. ACM, New York, NY, 45-58.