CS 2620 Distributed Systems

Lecture material

• Distributed systems
• The consensus problem
• Fisher-Lynch-Paterson impossibility
• Failure detectors and Chandra-Toueg consensus
• Paxos
• State machine replication
• Multi-Paxos
• PBFT

Problem sets

• Problem set 1
• Problem set 2
• Problem set 3
  • Problem set 3f: Failure model trades
• Problem set 4

Manuals

• Cotamer
• Cotamer I/O

Readings

• (optional) The Part-Time Parliament. Leslie Lamport. ACM TOCS 16(2), May 1998. (ACM link)
• Viewstamped replication revisited. Barbara Liskov and James Cowling. MIT-CSAIL-TR-2012-021, July 2012.
• (optional) In search of an understandable consensus algorithm [i.e., Raft]. Diego Ongaro and John Ousterhout. Proc. USENIX ATC 2014, June 2014. (authors’ extended version)
• The Chubby lock service for loosely-coupled distributed systems. Mike Burrows. Proc. USENIX OSDI 2006, Nov. 2006.
• Paxos Made Live—An Engineering Perspective. Tushar Chandra, Robert Griesemer, and Joshua Redstone. Proc. ACM PODC 2007, June 2007.
• Spanner: Google’s Globally-Distributed Database. James C. Corbett, Jeffrey Dean, Michael Epstein, et al. Proc. USENIX OSDI 2012, Oct. 2012.
• There Is More Consensus in Egalitarian Parliaments. Iulian Moraru, David G. Andersen, and Michael Kaminsky. Proc. ACM SOSP 2013, Nov. 2013.
• The Google File System. Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung. Proc. ACM SOSP 2003, Oct. 2003.
• Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services. Seth Gilbert and Nancy Lynch. ACM SIGACT News 33(2), June 2002.
• Millions of Tiny Databases. Marc Brooker, Tao Chen, and Fan Ping. Proc. USENIX NSDI 2020, Feb. 2020.
• Practical Byzantine Fault Tolerance. Miguel Castro and Barbara Liskov. Proc. USENIX OSDI 1999, Feb. 1999.
• Making Byzantine Fault Tolerant Systems Tolerate Byzantine Faults. Allen Clement, Edmund Wong, Lorenzo Alvisi, Mike Dahlin, and Mirco Marchetti. Proc. USENIX NSDI 2009, April 2009.
• The Saddest Moment. James Mickens. USENIX ;login:, May 2013.
• HotStuff: BFT Consensus with Linearity and Responsiveness. Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta, and Ittai Abraham. Proc. ACM PODC 2019, July 2019.
• Do Incentives Build Robustness in BitTorrent? Michael Piatek, Tomas Isdal, Thomas Anderson, Arvind Krishnamurthy, and Arun Venkataramani. Proc. USENIX NSDI 2007, April 2007.