CPS 512 (Duke University) Distributed * Systems
home calendar topics work resources
Class Meetings
TTh 1:25 - 2:40 in D106 LSRC
Jeff Chase (chase@cs.duke.edu)
Office hours: T 11AM, F 2PM, in D306 LSRC, or by appointment, or try a drop-in.
Teaching Assistant
Christopher Streiffer
TA Office hours: M 5-6PM, W 11:30 AM -1:00 PM, in D341 LSRC

Course announcements appear here.

  • 11/30: Reliable datacenter transactions. Slides: [reliable-actions.pptx] or [reliable-actions.pdf].
  • Midterm #2 solution: [PPTX], [PDF].
  • Some reading: Time, clocks, and the ordering of events. We won't discuss the material on physical clocks. Optional reading on logical time and vector clocks: Why Logical Clocks Are Easy [local PDF]. Bayou and asynchronous replication with vector clocks. Optional reading: SOSP95 [PDF]
  • 11/14, 21, 28: Logical+vector clocks and causal consistency. Slides: [rough-consistency.pptx] or [rough-consistency.pdf].
  • 11/9: guest speaker Chris Streiffer on Smart Contracts. Slides: [smart-contracts-streiffer-110917.pptx] or [smart-contracts-streiffer-110917.pdf].
  • On 11/7 we continue sloppy quorum in Dynamo, also known as "RWN replication". We also discuss the analysis of RWN in the Bailis et. al. paper on Probabilistic Bounded Staleness (PBS) [PDF] using the author's slides [PDF]
  • Midterm exam Thursday November 16 as planned!
  • Eventual consistency and sloppy quorum in Dynamo. Slides: [sloppy-quorum.pptx] or [sloppy-quorum.pdf].
  • Viewstamped Replication etc. (10/31). Slides: [vr+paxos.pptx] or [vr+paxos.pdf].
  • Reading for 10/31: From Viewstamped Replication to Byzantine Fault Tolerance [PDF]. We will talk about recovery in Consensus Replication (RSM), focusing on Viewstamped Replication (VR) and RAFT. Just focus on VR: save the BFT for later.
  • Midterm exam 1: [PPTX], [PDF]. Solution: [PPTX], [PDF].
  • Transactions: ACID, 2PL, 2PC, and all that. Slides: [transactions.pptx] or [transactions.pdf].
  • Reading for 10/24. To get some background on ACID transactions, please read the Franklin tutorial through section 3.1.1 (two-phase locking or 2PL). That is the first 17 pages (note: it is double-spaced). We will talk about client/server transaction systems and distributed transaction commit using two-phase commit (2PC). Unfortunately, Franklin does not get into distributed transactions. In Franklin, you can skim 2.2.2 on buffer management: we will discuss transaction logging for a NO-FORCE system that does not STEAL, as is typical of file systems and of transaction libraries that run in virtual memory. The remainder of the Franklin tutorial is a great source on the ARIES algorithm for transactions in a full-strength DBMS with STEAL. But it is out of our scope, so we won't discuss it: it is core material for the database class.
  • Project proposal deadline extended to 10/24.
  • 10/12-19: request routing and Slicer. Slides: [request-routing.pptx] or [request-routing.pdf].
  • Also for 10/17: Slicer author slides (see OSDI 2016 page for Slicer)
  • Sharding and request routing in mega-services (For 10/12-19). We will talk about several systems together, focusing on Google's Slicer (OSDI 16) as an alternative to the consistent hashing approach used in Akamai (Algorithmic Nuggets in Content Delivery [PDF]), DHTs, and the canonical Dynamo key-value store [PDF]. Also a little more on Google's Borg (Eurosys15), which is the platform for services running under Slicer, and sharding in services including Google's GFS [PDF] and scalable DNS. Together these should give a complete picture of how requests are distributed in mega-services. To illustrate from Facebook, we will also discuss Kraken (OSDI 16) briefly.

CPS 512 is a graduate-level course dealing with techniques for storing and sharing information in computer networks, large and small. We will cover a range of core distributed systems topics, with an emphasis on the issues faced by cloud platforms, scalable Internet services, and distributed storage systems. The course is suitable for advanced undergraduates.

Course synopsis
Topics and readings [PDF]
Syllabus [PDF] required by Duke policy. Any changes to the information in the syllabus will be announced, and a dated revision of the syllabus provided.
Exam policies
CPS 512 exam archive