CPS 512 (Duke University) Distributed Systems
home calendar topics work resources

CPS 512 focuses on core concepts in distributed systems, using cloud platforms for megaservices as a motivation and driving example. Well-designed cloud applications are layered above common service platforms that handle the hard problems: tracking groups of participating servers (views), distributing state and functions across a group, coordinating control and ownership of data, storing data reliably, and recovering from server and network failures. The course focuses on the design of these service platforms and their abstractions.

Although the course covers the fundamentals, the emphasis is on practical technologies and their limitations with an important software technology component. Assigned projects are based on DSLabs from the University of Washington (by way of MIT).

The readings for the course include some tutorial and survey papers, with a handful of full-strength research papers, including systems papers from major cloud services companies (e.g., Amazon, Google, and Facebook). There is no textbook.

Here is an outline of topics and readings for the course. Each section corresponds to a course unit and each bullet corresponds roughly to one class. An offering of CPS 512 selects from these topics according to circumstances of the semester and class, and assigns a subset of the recommended readings below, and others.

Reliable communication and services in the client/server model

Structure of distributed systems: networking, naming and addressing, clients and servers, request/response (Web/HTTP) and Remote Procedure Call (RPC), multi-tier services, geo-distributed mega-services. Messaging, failure models, and the problem of network partitions. State and the data storage tier.

Scalable services, reliability, and consistency

Elastic services in the cloud

Coordination, consistency, and consensus

We spend a few days discussing consensus in theory and in practice. A safe, live consensus algorithm is the cornerstone of reliable distributed systems. But it is impossible to build one! So this is a study of what works in practice.

Distributed transactions

Atomic transactions are fundamental for managing complex shared state. Early datacenter stacks avoided ACID transactions in favor of BASE key-value stores such as Dynamo. Modern key-value stores incorporate client/server transactions following the Thor model, with many variations. DSLabs Lab 4 features a transactional key-value store with sharding and replication, following many elements of RAMCloud/RIFL.

Causality and eventual consistency

CAP tells us that systems built for high availability in demanding environments (unreliable networks) must compromise consistency. But how? How to build ”AP” systems and applications that function correctly even without synchronous communication with a quorum-approved master? We need a weaker notion of consistency based on causal orderings and a deeper understanding of concurrency and update conflicts.

Trust in networked systems

We shift focus to secure Internet-scale systems with multiple identities, multiple trust domains, and federation. Multi-domain systems integrate cryptographic primitives to defend against subversion and unfaithful behavior by malicious participants. They include defenses against Byzantine faults, in which failed nodes may lie or cheat.


[1]   A. Adya, D. Myers, J. Howell, J. Elson, C. Meek, V. Khemani, S. Fulger, P. Gu, L. Bhuvanagiri, J. Hunter, et al. Slicer: Auto-sharding for datacenter applications. In 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI), pages 739–753, 2016.

[2]   P. Bailis and A. Ghodsi. Eventual consistency today: Limitations, extensions, and beyond. Commun. ACM, 56(5):55–63, May 2013. [local pdf].

[3]   P. Bailis, S. Venkataraman, M. J. Franklin, J. M. Hellerstein, and I. Stoica. Quantifying eventual consistency with PBS. Communications of the ACM, 57(8):93–102, Aug. 2014. [local pdf].

[4]   C. Baquero and N. Preguiça. Why logical clocks are easy. Communications of the ACM, 59(4):43–47, 2016. [local pdf].

[5]   A. Birrell and B. Nelson. Implementing Remote Procedure Calls. ACM Transactions on Computer Systems (TOCS), 2(1):39–59, 1984. [local pdf].

[6]   E. Brewer. CAP twelve years later: How the “rules” have changed. Computer, 45(2):23–29, February 2012. [local pdf].

[7]   M. Burrows. The Chubby lock service for loosely-coupled distributed systems. In Proceedings of the 7th Symposium on Operating Systems Design and Implementation (OSDI), pages 335–350. USENIX Association, May 2006. [local pdf].

[8]   M. Burrows, M. Abadi, and R. Needham. A logic of authentication. ACM Transactions on Computing Systems (TOCS), 8(1):18–36, 1990. [local pdf].

[9]   J. Dean and L. A. Barroso. The tail at scale. Communications of the ACM, 56(2):74–80, 2013.

[10]   G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels. Dynamo: Amazon’s highly available key-value store. In SOSP ’07: Proceedings of 21st ACM SIGOPS Symposium on Operating systems Principles, pages 205–220, New York, NY, USA, 2007. ACM. [local pdf].

[11]   M. J. Franklin. Concurrency controland recovery, 1997. [local pdf].

[12]   S. Ghemawat, H. Gobioff, and S.-T. Leung. The Google File System. In SOSP ’03: Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles, pages 29–43, New York, NY, USA, October 2003. ACM. [local pdf].

[13]   L. Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7):558–565, 1978. [local pdf].

[14]   B. W. Lampson. How to build a highly available system using consensus. In Distributed Algorithms, pages 1–17. Springer, 1996. [local pdf].

[15]   C. Lee, S. J. Park, A. Kejriwal, S. Matsushita, and J. Ousterhout. Implementing linearizability at large scale and low latency. In Proceedings of the 25th Symposium on Operating Systems Principles (SOSP), pages 71–86, 2015.

[16]   B. Liskov. Practical uses of synchronized clocks in distributed systems. In Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, PODC ’91, pages 1–9, New York, NY, USA, 1991. ACM. [local pdf].

[17]   B. Liskov. From viewstamped replication to byzantine fault tolerance. In Replication, pages 121–149. Springer, 2010. [local pdf].

[18]   D. Ongaro and J. Ousterhout. In search of an understandable consensus algorithm. In Proceedings of the USENIX Annual Technical Conference, pages 305–320, June 2014. [local pdf].

[19]   K. Petersen, M. Spreitzer, D. Terry, and M. Theimer. Bayou: Replicated database services for world-wide applications. In Proceedings of the 7th ACM SIGOPS European Workshop: Systems Support for Worldwide Applications, pages 275–280. ACM, September 1996. [local pdf].

[20]   K. Petersen, M. J. Spreitzer, D. B. Terry, M. M. Theimer, and A. J. Demers. Flexible update propagation for weakly consistent replication. In SOSP ’97: Proceedings of the Sixteenth ACM Symposium on Operating systems Principles, pages 288–301, New York, NY, USA, October 1997. ACM. [local pdf].

[21]   R. Van Renesse and D. Altinbuken. Paxos made moderately complex. ACM Computing Surveys, 47(3):42:1–42:36, Feb. 2015. [local pdf].