Ordering

• L. Lamport. Time, Clocks, and the Ordering of Events in a Distributed System. Communications of the ACM, July 1978, pages 558-564.
• Optional:
  • Friedemann Mattern. Virtual Time and Global States of Distributed Systems. 1988.
  • M. Chandy and L. Lamport. Distributed Snapshots: Determining Global States of Distributed Systems. ACM Trans. Comput. Syst., 3(1):63-75, 1985.

Consensus

• Leslie Lamport. Paxos Made Simple. ACM SIGACT News, 2001.
• Diego Ongaro and John Ousterhout. In Search of an Understandable Consensus Algorithm (Extended Version). In 2014 USENIX Annual Technical Conference (ATC 14), 2014.
• Barbara Liskov and James Cowling. Viewstamped replication revisited. 2012.
• Optional:
  • Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. 1985. Impossibility of distributed consensus with one faulty process. J. ACM 32, 2 (April 1985), 374–382.
  • Fred B. Schneider. Implementing fault-tolerant services using the state machine approach: A tutorial. ACM Computing Surveys (CSUR) 22.4 (1990): 299-319.
  • Navin Budhiraja, Keith Marzullo, Fred B. Schneider, and Sam Toueg. Optimal Primary-Backup Protocols. International Workshop on Distributed Algorithms. Springer, Berlin, Heidelberg, 1992.

Paxos optimizations

• Aishwarya Ganesan, Ramnatthan Alagappan, Andrea Arpaci-Dusseau, Remzi Arpaci-Dusseau Exploiting Nil-Externality of Fast Replicated Storage. SOSP 2021.
• Charapko, Aleksey, Ailidani Ailijiang, and Murat Demirbas. "Linearizable quorum reads in Paxos." In 11th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage 19). 2019.
• Optional:
  • Moraru, Iulian, David G. Andersen, and Michael Kaminsky. "Paxos quorum leases: Fast reads without sacrificing writes." In Proceedings of the ACM Symposium on Cloud Computing, pp. 1-13. 2014.

Shared registers

• H. Attiya, A. Bar-Noy, and D. Dolev. Sharing Memory Robustly in Message-Passing Systems. Journal of the ACM (JACM), 42(1):124–142, 1995.

Paxos optimizations (cont.)

• Dan RK Ports, Jialin Li, Vincent Liu, Naveen Kr Sharma, and Arvind Krishnamurthy. Designing distributed systems using approximate synchrony in data center networks. In 12th USENIX Symposium on Networked Systems Design and Implementation (NSDI 15). 2015.
• Seo Jin Park and John Ousterhout. 2019. Exploiting Commutativity For Practical Fast Replication. In Proceedings of the 16th Symposium on Networked Systems Design and Implementation (NSDI ’19).
• Manos Kapritsos, Yang Wang, Vivien Quema, Allen Clement, Lorenzo Alvisi, and Mike Dahlin. 2012. All About Eve: Execute-verify Replication for Multi-core Servers. In Proceedings of the 10th Symposium on Operating Systems Design and Implementation (OSDI ’12).
• Optional:
  • Leslie Lamport. 2005. Fast paxos. MSR-TR-2005-112.
  • Leslie Lamport. 2005. Generalized Consensus and Paxos. (2005).

Consensus in Practice

• Bolosky, William J., Dexter Bradshaw, Randolph B. Haagens, Norbert P. Kusters, and Peng Li. Paxos Replicated State Machines as the Basis of a High-Performance Data Store. NSDI 11. 2011.
• Tushar D Chandra, Robert Griesemer, and Joshua Redstone. Paxos Made Live: An Engineering Perspective. PODC 07.
• Mike Burrows. The Chubby Lock Service for Loosely-Coupled Distributed Systems. OSDI 2006.
• Optional:
  • Patrick Hunt, Mahadev Konar, Flavio Paiva Junqueira, and Benjamin Reed. ZooKeeper: Wait-free Coordination for Internet-scale Systems. In USENIX annual technical conference (ATC), 2010.

Byzantine

• L. Lamport, R. Shostak, and M. Pease. The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems, July 1982, pages 382-401.
• Miguel Castro and Barbara Liskov. Practical Byzantine Fault Tolerance. OSDI, 1999.
• Optional:
  • Ramakrishna Kotla, Lorenzo Alvisi, Mike Dahlin, Allen Clement, and Edmund Wong. Zyzzyva: Speculative Byzantine Fault Tolerance. SOSP 2007.

Distributed transactions

• Butler Lampson, and David B. Lomet. A new presumed commit optimization for two phase commit. VLDB. Vol. 93. 1993.
• Corbett et al. Spanner: Google's Globally-Distributed Database. OSDI 2012.
• Irene Zhang, Naveen Kr. Sharma, Adriana Szekeres, Arvind Krishnamurthy, and Dan R. K. Ports. Building Consistent Transactions with Inconsistent Replication. SOSP 2015.
• Adriana Szekeres, Michael Whittaker, Jialin Li, Naveen Kr Sharma, Arvind Krishnamurthy, Dan RK Ports, Irene Zhang. Meerkat: multicore-scalable replicated transactions following the zero-coordination principle.

Consistency models

• Douglas Terry. Replicated data consistency explained through baseball. Communications of the ACM, Dec 2013.
• Eric Brewer. CAP Theorem. PODC Keynote, 2000.
• Viotti, P. and Vukolić, M., 2016. Consistency in non-transactional distributed storage systems. ACM Computing Surveys (CSUR), 49(1), pp.1-34.
• Linearizability:
  • Maurice P. Herlihy, and Jeannette M. Wing. "Linearizability: A correctness condition for concurrent objects." ACM Transactions on Programming Languages and Systems (TOPLAS) 12, no. 3 (1990): 463-492.
  • Collin Lee, Seo Jin Park, Ankita Kejriwal, Satoshi Matsushita, and John Ousterhout. Implementing Linearizability at Large Scale and Low Latency. In Proceedings of the 25th Symposium on Operating Systems Principles (SOSP), 2015.
• Causal consistency:
  • Wyatt Lloyd, Michael J. Freedman, Michael Kaminsky, and David G. Andersen. Don't settle for eventual: scalable causal consistency for wide-area storage with COPS. In Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles (SOSP), 2011.
  • Syed Akbar Mehdi, Cody Littley, Natacha Crooks, Lorenzo Alvisi, Nathan Bronson, and Wyatt Lloyd. I can't believe it's not causal! scalable causal consistency with no slowdown cascades. In 14th USENIX Symposium on Networked Systems Design and Implementation (NSDI 17), 2017.
• Eventual consistency:
  • Terry et al. Managing update conflicts in Bayou, a weakly connected replicated storage system. SOSP, 1995.
  • Lu et al. Existential consistency: measuring and understanding consistency at Facebook. In Proceedings of the 25th Symposium on Operating Systems Principles (SOSP), 2015.
  • Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swami Sivasubramanian, Peter Vosshall and Werner Vogels. Dynamo: Amazon's Highly Available Key-Value Store. Proceedings of the 21st ACM Symposium on Operating Systems Principles, Stevenson, WA, October 2007
• Read your writes
  • Xiao Shi, Scott Pruett, Kevin Doherty, Jinyu Han, Dmitri Petrov, Jim Carrig, John Hugg, and Nathan Bronson. Flighttracker: Consistency across read-optimized online stores at facebook.

Student presentations

Geo-replication, Leaderless, Multi-threaded execution

• Iulian Moraru, David G. Andersen, and Michael Kaminsky. There is more consensus in egalitarian parliaments. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles (SOSP), 2013.
• Manos Kapritsos, Yang Wang, Vivien Quema, Allen Clement, Lorenzo Alvisi, and Mike Dahlin. 2012. All About Eve: Execute-verify Replication for Multi-core Servers. OSDI 12.

Shared logs

• Joshua Lockerman, Jose M. Faleiro, Juno Kim, Soham Sankaran, Daniel J. Abadi, James Aspnes, Siddhartha Sen, and Mahesh Balakrishnan. 2018. The FuzzyLog: A Partially Ordered Shared Log. OSDI 18.
• Mahesh Balakrishnan et al. Virtual Consensus in Delos. OSDI 2020.

New hardware: RDMA + disaggregated memory

• Marcos K Aguilera, Naama Ben-David, Rachid Guerraoui, Virendra J Marathe, Athanasios Xygkis, and Igor Zablotchi. Microsecond consensus for microsecond applications. OSDI 20.
• Yang Zhou, Hassan M. G. Wassel, Sihang Liu, Jiaqi Gao, James Mickens, Minlan Yu, Chris Kennelly, Paul Turner, David E. Culler, Henry M. Levy, and Amin Vahdat. 2022. Carbink: Fault-Tolerant Far Memory. OSDI 22.

Distributed transactions for new hardware: Programmable switches and NICs

• J. Li, E. Michael, and D. R. K. Ports. Eris: Coordination free consistent transactions using in-network concurrency control. SOSP 17.
• Henry N. Schuh, Weihao Liang, Ming Liu, Jacob Nelson, and Arvind Krishnamurthy. 2021. Xenic: SmartNIC-Accelerated Distributed Transactions. SOSP 21.

Distributed FS for modern hardware

• Thomas E. Anderson, Marco Canini, Jongyul Kim, Dejan Kostic, Youngjin Kwon, Simon Peter, Waleed Reda, Henry N. Schuh, and Emmett Witchel. Assise: Performance and Availability via Client-local NVM in a Distributed File System. OSDI 20.
• YJongyul Kim, Insu Jang, Waleed Reda, Jaeseong Im, Marco Canini, Dejan Kostić, Youngjin Kwon, Simon Peter, Emmett Witchel. LineFS: Efficient SmartNIC Offload of a Distributed File System with Pipeline Parallelism. SOSP 21.

Virtual Machine Fault-Tolerance

• Daniel J. Scales, Mike Nelson, and Ganesh Venkitachalam The Design of a Practical System for Fault-Tolerant Virtual Machines. OSR 2010.
• Brendan Cully, Geoffrey Lefebvre, Dutch Meyer, Mike Feeley, Norm Hutchinson, and Andrew Warfield. Remus: High availability via asynchronous virtual machine replication. In Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation (NSDI), pp. 161-174. 2008.

Fault tolerance for in-memory computing

• Matei Zaharia, Mosharaf Chowdhury, Tathagata Das, Ankur Dave, Justin Ma, Murphy McCauley, Michael J. Franklin, Scott Shenker, Ion Stoica. Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing. NSDI 2012. April 2012.
• Stephanie Wang, John Liagouris, and Robert Nishihara. 2019. Lineage stash: Fault tolerance off the critical path. SOSP 19.