CS 7670 (2024 FA)

Academic papers in the field will be discussed during class.

* The papers to be discussed are subject to change.

* All papers listed here can be accessed directly through the publisher website or through the Northeastern library (you will need to log in with your Northeastern account NetID; search for ACM digital library or IEEE Xplore depending on the publisher; and search the paper within the online tools).

* Papers in bold text are for critique assignments.

Schedule

Week 1 (lecture) - week of 09/02

Introduction and course logistics [slides]

Week 2 (lecture) - week of 09/09

Problems and considerations in distributed systems [slides from the previous lecture]
Failures and datacenters [slides]

Week3 (lecture) - week of 09/16

Replication, ACID, BASE, CAP [slides]

Week 4 (discussion) - week of 09/23

Chain replication, CRAQ (Ji-Yong) [slides]
- Robbert van Renesse and Fred B. Schneider. 2004. Chain replication for supporting high throughput and availability. In Proceedings of the 6th conference on Symposium on Operating Systems Design & Implementation - Volume 6 (OSDI'04). USENIX Association, USA, 7.
- Jeff Terrace and Michael J. Freedman. 2009. Object storage on CRAQ: high-throughput chain replication for read-mostly workloads. In Proceedings of the 2009 conference on USENIX Annual technical conference (USENIX'09). USENIX Association, USA, 11.
Corfu and Tango (David)
- Mahesh Balakrishnan, Dahlia Malkhi, John D. Davis, Vijayan Prabhakaran, Michael Wei, and Ted Wobber. 2013. CORFU: A distributed shared log. ACM Trans. Comput. Syst. 31, 4, Article 10 (December 2013), 24 pages. https://doi.org/10.1145/2535930
- Mahesh Balakrishnan, Dahlia Malkhi, Ted Wobber, Ming Wu, Vijayan Prabhakaran, Michael Wei, John D. Davis, Sriram Rao, Tao Zou, and Aviad Zuck. 2013. Tango: distributed data structures over a shared log. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles (SOSP '13). Association for Computing Machinery, New York, NY, USA, 325–340. https://doi.org/10.1145/2517349.2522732

Week 5 (discussion) - week of 09/30

Time in distributed systems and totally ordered multicast (Ji-Yong) [slides]
- Leslie Lamport. 1978. Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21, 7 (July 1978), 558–565. https://doi.org/10.1145/359545.359563
- Friedemann Mattern, "Virtual Time and Global States of Distributed Systems", Workshop on Parallel and Distributed Algorithms, Elsevier, pp. 215–226, 1989
- Colin J. Fidge, "Timestamps in Message-Passing Systems That Preserve the Partial Ordering". 11th Australian Computer Science Conference. pp. 56–66, 1988.
- Xavier Défago, André Schiper, and Péter Urbán. 2004. Total order broadcast and multicast algorithms: Taxonomy and survey. ACM Comput. Surv. 36, 4 (December 2004), 372–421. https://doi.org/10.1145/1041680.1041
FuzzyLog (Alan) [slides]
- 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. In Proceedings of the 13th USENIX conference on Operating Systems Design and Implementation (OSDI'18). USENIX Association, USA, 357–372.

Week 6 (discussion) - week of 10/07

Session guarantees (Ji-Yong) [slides]
- Douglas B. Terry, Alan J. Demers, Karin Petersen, Mike Spreitzer, Marvin Theimer, and Brent W. Welch. 1994. Session Guarantees for Weakly Consistent Replicated Data. In Proceedings of the Third International Conference on Parallel and Distributed Information Systems (PDIS '94). IEEE Computer Society, USA, 140–149.
- Doug Terry. 2013. Replicated data consistency explained through baseball. Commun. ACM 56, 12 (December 2013), 82–89. https://doi.org/10.1145/2500500
Bayou and Pileus (Yifei) [slides]
- D. B. Terry, M. M. Theimer, Karin Petersen, A. J. Demers, M. J. Spreitzer, and C. H. Hauser. 1995. Managing update conflicts in Bayou, a weakly connected replicated storage system. In Proceedings of the fifteenth ACM symposium on Operating systems principles (SOSP '95). Association for Computing Machinery, New York, NY, USA, 172–182. https://doi.org/10.1145/224056.224070
- Douglas B. Terry, Vijayan Prabhakaran, Ramakrishna Kotla, Mahesh Balakrishnan, Marcos K. Aguilera, and Hussam Abu-Libdeh. 2013. Consistency-based service level agreements for cloud storage. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles (SOSP '13). Association for Computing Machinery, New York, NY, USA, 309–324. https://doi.org/10.1145/2517349.2522731

Week 7 (discussion) - week of 10/14

Causal consistency (Ji-Yong) [slides]
- Ahamad, M., Neiger, G., Burns, J.E. et al. Causal memory: definitions, implementation, and programming. Distrib Comput 9, 37–49 (1995). http://hdl.handle.net/1853/6781
- P. W. Hutto and M. Ahamad, "Slow memory: weakening consistency to enhance concurrency in distributed shared memories," Proceedings.,10th International Conference on Distributed Computing Systems, Paris, France, 1990, pp. 302-309, doi: 10.1109/ICDCS.1990.89297.
- Peter Bailis, Alan Fekete, Ali Ghodsi, Joseph M. Hellerstein, and Ion Stoica. 2012. The potential dangers of causal consistency and an explicit solution. In Proceedings of the Third ACM Symposium on Cloud Computing (SoCC '12). Association for Computing Machinery, New York, NY, USA, Article 22, 1–7. https://doi.org/10.1145/2391229.2391251
COPS (David) [slides]
- Wyatt Lloyd, Michael J. Freedman, Michael Kaminsky, and David G. Andersen. 2011. 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 '11). Association for Computing Machinery, New York, NY, USA, 401–416. https://doi.org/10.1145/2043556.2043593

Week 8 (discussion) - week of 10/21

Atomic commit - ABD protocol (Ji-Yong) [slides]
- Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. 1990. Sharing memory robustly in message-passing systems. In Proceedings of the ninth annual ACM symposium on Principles of distributed computing (PODC '90). Association for Computing Machinery, New York, NY, USA, 363–375. https://doi.org/10.1145/93385.93441
DynaStore and RAMBO (Alan) [slides]
- Marcos Kawazoe Aguilera, Idit Keidar, Dahlia Malkhi, and Alexander Shraer. 2009. Dynamic atomic storage without consensus. In Proceedings of the 28th ACM symposium on Principles of distributed computing (PODC '09). Association for Computing Machinery, New York, NY, USA, 17–25. https://doi.org/10.1145/1582716.1582726
- Gilbert, S., Lynch, N.A. & Shvartsman, A.A. Rambo: a robust, reconfigurable atomic memory service for dynamic networks. Distrib. Comput. 23, 225–272 (2010). https://doi.org/10.1007/s00446-010-0117-1

Week 9 (discussion) - week of 10/28

2PC / 3PC (Ji-Yong) [slides]
- Birman, K.P. (2012). Overcoming Failures in a Distributed System. In: Guide to Reliable Distributed Systems. Texts in Computer Science. Springer, London. https://doi-org.ezproxy.neu.edu/10.1007/978-1-4471-2416-0_10
Sinfonia (Yifei) [slides]
- Marcos K. Aguilera, Arif Merchant, Mehul Shah, Alistair Veitch, and Christos Karamanolis. 2007. Sinfonia: a new paradigm for building scalable distributed systems. In Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles (SOSP '07). Association for Computing Machinery, New York, NY, USA, 159–174. https://doi.org/10.1145/1294261.1294278

Week 10 (discussion) - week of 11/04

Paxos (Ji-Yong) [slides]
- Lamport, L. Paxos Made Simple. ACM SIGACT News (Distributed Computing Column) 32, 4 (Whole Number 121, December 2001), December, 2001. https://www.microsoft.com/en-us/research/uploads/prod/2016/12/paxos-simple-Copy.pdf
- Leslie Lamport. 1998. The part-time parliament. ACM Trans. Comput. Syst. 16, 2 (May 1998), 133–169. https://doi.org/10.1145/279227.279229
- Robbert Van Renesse and Deniz Altinbuken. 2015. Paxos Made Moderately Complex. ACM Comput. Surv. 47, 3, Article 42 (April 2015), 36 pages. https://doi.org/10.1145/2673577
- Wolf Honoré, Jieung Kim, Ji-Yong Shin, and Zhong Shao. 2021. Much ADO about failures: a fault-aware model for compositional verification of strongly consistent distributed systems. Proc. ACM Program. Lang. 5, OOPSLA, Article 97 (October 2021), 31 pages. https://doi.org/10.1145/3485474
Raft (David) [slides]
- Diego Ongaro and John Ousterhout. 2014. In search of an understandable consensus algorithm. In Proceedings of the 2014 USENIX conference on USENIX Annual Technical Conference (USENIX ATC'14). USENIX Association, USA, 305–320. https://www.usenix.org/system/files/conference/atc14/atc14-paper-ongaro.pdf
- Zhaoguo Wang, Changgeng Zhao, Shuai Mu, Haibo Chen, and Jinyang Li. 2019. On the Parallels between Paxos and Raft, and how to Port Optimizations. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC '19). Association for Computing Machinery, New York, NY, USA, 445–454. https://doi.org/10.1145/3293611.3331595

Week 11 (discussion) - week of 11/11

Consensus on transaction commit - 2PC + Consensus (Ji-Yong) [slides]
- Jim Gray and Leslie Lamport. 2006. Consensus on transaction commit. ACM Trans. Database Syst. 31, 1 (March 2006), 133–160. https://doi.org/10.1145/1132863.1132867
Tapir, Rococo (Alan) [slides]
- Irene Zhang, Naveen Kr. Sharma, Adriana Szekeres, Arvind Krishnamurthy, and Dan R. K. Ports. 2015. Building consistent transactions with inconsistent replication. In Proceedings of the 25th Symposium on Operating Systems Principles (SOSP '15). Association for Computing Machinery, New York, NY, USA, 263–278. https://doi.org/10.1145/2815400.2815404
- Shuai Mu, Yang Cui, Yang Zhang, Wyatt Lloyd, and Jinyang Li. 2014. Extracting more concurrency from distributed transactions. In Proceedings of the 11th USENIX conference on Operating Systems Design and Implementation (OSDI'14). USENIX Association, USA, 479–494.

Week 12 (discussion) - week of 11/18

Randomized consensus (Ji-Yong) [slides]
- Aspnes, J. Randomized protocols for asynchronous consensus. Distrib. Comput. 16, 165–175 (2003). https://doi.org/10.1007/s00446-002-0081-5
Rabia (Yifei) [slides]
- Haochen Pan, Jesse Tuglu, Neo Zhou, Tianshu Wang, Yicheng Shen, Xiong Zheng, Joseph Tassarotti, Lewis Tseng, and Roberto Palmieri. 2021. Rabia: Simplifying State-Machine Replication Through Randomization. In Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles (SOSP '21). Association for Computing Machinery, New York, NY, USA, 472–487. https://doi.org/10.1145/3477132.3483582

Week 13 (discussion) - week of 11/25 (Thanksgiving/Fall break)

Byzantine consensus and blockchains (Ji-Yong)
- Miguel Castro and Barbara Liskov. 1999. Practical Byzantine fault tolerance. In Proceedings of the third symposium on Operating systems design and implementation (OSDI '99). USENIX Association, USA, 173–186. https://pmg.csail.mit.edu/papers/osdi99.pdf
- Nakamoto, Satoshi. "Bitcoin: A peer-to-peer electronic cash system." Satoshi Nakamoto (2008).

Week 14 (discussion) - week of 12/02

HotStuff (David)
- Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta, and Ittai Abraham. 2019. HotStuff: BFT Consensus with Linearity and Responsiveness. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC '19). Association for Computing Machinery, New York, NY, USA, 347–356. https://doi.org/10.1145/3293611.3331591

Week 15 - week of 12/09

Project presentations

Page updated

Google Sites

Report abuse