Ordering

• 1/21: 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

• 1/23: Leslie Lamport. Paxos Made Simple. ACM SIGACT News, 2001.
• 1/30: Diego Ongaro and John Ousterhout. In Search of an Understandable Consensus Algorithm (Extended Version). In 2014 USENIX Annual Technical Conference (ATC 14), 2014.
• 2/6: 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.
  • 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/variants

• 2/11: 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.
• 2/13: 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).
• Optional:
  • Leslie Lamport. 2005. Fast paxos. MSR-TR-2005-112.
  • Leslie Lamport. 2005. Generalized Consensus and Paxos. (2005).
  • 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.
  • 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.
  • 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).
  • 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.

Byzantine

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

Consensus: Practice

• 2/25: 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.
• 2/25: 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.
  • Tushar D Chandra, Robert Griesemer, and Joshua Redstone. Paxos Made Live: An Engineering Perspective. PODC 07.

Consistency models

• 2/27:Douglas Terry. Replicated data consistency explained through baseball. Communications of the ACM, Dec 2013.
• 2/27:Eric Brewer. CAP Theorem. PODC Keynote, 2000.
• 3/4: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.
• 3/6:Terry et al. Managing update conflicts in Bayou, a weakly connected replicated storage system. SOSP, 1995.
• 3/11: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
• Optional:
  • 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.
  • 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:
    • Lu et al. Existential consistency: measuring and understanding consistency at Facebook. In Proceedings of the 25th Symposium on Operating Systems Principles (SOSP), 2015.
  • 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.

Distributed transactions

• 3/25:Butler Lampson, and David B. Lomet. A new presumed commit optimization for two phase commit. VLDB. Vol. 93. 1993.
• 3/27:Corbett et al. Spanner: Google's Globally-Distributed Database. OSDI 2012.
• Optional:
  • 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.

Shared logs

• 4/1: Mahesh Balakrishnan, Dahlia Malkhi, Vijayan Prabhakaran, Ted Wobber, Michael Wei, and John D. Davis. C.CORFU: A Shared Log Design for Flash Clusters
• 4/1: Cong Ding, David Chu, Evan Zhao, Xiang Li, Lorenzo Alvisi, and Robbert Van Renesse. Scalog: Seamless Reconfiguration and Total Order in a Scalable Shared Log
• Optional:
  • 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.

Student presentations

New hardware: RDMA, disaggregated memory

• 4/3:Marcos K Aguilera, Naama Ben-David, Rachid Guerraoui, Virendra J Marathe, Athanasios Xygkis, and Igor Zablotchi. Microsecond consensus for microsecond applications. OSDI 20.
• 4/3: Murat et al. SWARM: Replicating Shared Disaggregated-Memory Data in No Time. SOSP 2024.
• 4/8: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.
• 4/8: Zhang et al. Partial Failure Resilient Memory Management System for (CXL-based) Distributed Shared Memory . SOSP 23.

Optional: other emerging hardware

• Wang et al. Replicating Persistent Memory Key-Value Stores with Efficient RDMA Abstraction. OSDI 2023.
• 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.
• 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

• 4/10: Daniel J. Scales, Mike Nelson, and Ganesh Venkitachalam The Design of a Practical System for Fault-Tolerant Virtual Machines. OSR 2010.
• 4/10: 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-tolerant computing

• 4/15: Stephanie Wang, John Liagouris, and Robert Nishihara. 2019. Lineage stash: Fault tolerance off the critical path. SOSP 19.
• 4/15: Li et al. DARQ Matter Binds Everything: Performant and Composable Cloud Programming via Resilient Steps. SIGMOD 23.
• 4/22: Haoran Zhang, Adney Cardoza, Peter Baile Chen, Sebastian Angel, and Vincent Liu. 2020. Fault-tolerant and transactional stateful serverless workflows. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20). USENIX Association, 1187–1204. .
• 4/22: Jia et al. Boki: Towards Data Consistency and Fault Tolerance with Shared Logs in Stateful Serverless Computing. SOSP 21.

Fault-tolerant Training

• 4/24: Eisenman et al. Check-N-Run: a Checkpointing System for Training Deep Learning Recommendation Models. NSDI 22.
• 4/24: Wang et al. Gemini: Fast Failure Recovery in Distributed Training with In-Memory Checkpoints. SOSP 23.
• 4/29: Jang et al. Oobleck: Resilient Distributed Training of Large Models Using Pipeline Templates. SOSP 23.
• 4/29: Gandhi et al. ReCycle: Resilient Training of Large DNNs using Pipeline Adaptation. SOSP 24.