Tentative Course Schedule

>
12/6: Lab 4.3 due

Week	Monday	Wednesday	Friday	Assignment	Readings & Notes
8/26, 8/28, 8/30	Intro - 2 Generals Problem	Event Ordering and Global Predicate Detection	Lab 0/1 Intro	Lab assignments are accessible through the DSL Labs web site Labs 0/1 out	Class Notes for M/W Required readings: E. Michael et al. Teaching Rigorous Distributed Systems with Efficient Model Checking J. Halpern and Y. Moses Knowledge and Common Knowledge in a Distributed Environment (up to Section 4 included -- but feel free to keep going!) E.W. Dijkstra Prize 2009.
9/2, 9/4, 9/6	Labor Day	Lamport Clocks, Snapshot Protocol	Lab 2 Intro	9/6: Labs 1 design doc due Lab 1 due Lab 2 out	Class Notes for WW Required readings: O. Babaoglu and K. Marzullo Consistent Global States of Distributed Systems Chapter 4 of Sape Mullender's Distributed Systems, 2nd Edition. To know more: K. M. Chandy and L. Lamport Distributed Snapshots: Determining Global States of Distributed Systems SIGOPS Hall of Fame and E.W. Dijkstra Prize 2014.
9/9, 9/11, 9/13	Causal Order, Vector Clocks	Detecting non-stable properties	Lab 2 discussion	9/13: Lab 2 design doc due HW 1 Out	Class Notes for Monday and Wednesday
9/16, 9/18, 9/20	State Machine Replication	Primary Backup	Lab 2 Discussion	Lab 2 design doc feedback out 9/20: HW 1 due	Class Notes Required readings: R. van Renesse and F.B. Schneider Chain Replication for Supporting High Throughput and Availability T. Bressoud and F.B. Schneider Hypervisor-based Fault-Tolerance Best Paper Award, SOSP 95 To know more: F.B. Schneider The State Machine Approach SIGOPS Hall of Fame
9/23, 9/25, 9/27	Consensus and TRB	Consensus and TRB Paxos	Lab 3 Intro	9/27: Lab 2 due Lab 3 out	Class Notes for Monday and Wednesday Required readings: R. van Renesse Paxos made moderately complex To know more: L. Lamport Paxos Made Simple L. Lamport The Part-Time Parliament SIGOPS Hall of Fame
9/30, 10/2, 10/4	Paxos	Consensus lower bounds Logging and Rollback Recovery	Lab 3 discussion	10/4: HW 2 out	Class Notes To know more: E. Elnozahy, L. Alvisi, Y. M.Wang, and D. B. Johnson A Survey of Rollback Recovery Protocols in Message Passing Systems
10/7, 10/9, 10/11	Logging and Rolback Recovery	FLP	Lab 3 Discussion	10/7: Lab 3 design doc due 10/11:Lab 3 design doc feedback out 10/11: H2 due	Class Notes Required readings: D. Lee, B. Wester, K. Veeraraghavan, S. Narayanasamy, P. M. Chen, and J. Flinn Respec: Efficient Online Multiprocessor Replay via Speculation and External Determinism K. Veeraraghavan, D. Lee, B. Wester, J. Ouyang, P. M. Chen, J. Flinn, and S. Narayanasamy DoublePlay: Parallelizing Sequential Logging and Replay To know more: M. Fisher, N. Lynch, M. Paterson Impossibility of Consensus E.W.Dijkstra Prize, 2001.
10/14, 10/16, 10/18	Fall Break	Midterm	Lab 3 discussion		Required readings: P. Bernstein, N. Goodman, and V. Hadzilakos Distributed Recovery To know more: D. Skeen Non-blocking Commit Protocols D. Skeen Determining the Last Process to Fail
10/21, 10/23, 10/25	Atomic Commit	3 Phase Commit Last Process to Fail	Lab 4.1 intro	10/25: Lab 3 due Lab 4.1 out	Class Notes To know more: M. P. Herlihy and J. Wing Linearizability: A Correctness Condition for Concurrent Objects
10/28, 10/30, 11/1	Spanner	Weakly consistent systems		11/1: design document due	Class Notes Required readings: J.C. Corbett et al Spanner: Google's Globally Distributed Database G. DeCandia et al. Dynamo: Amazon's highly available key-value store Best Paper Award, SOSP 2007. W. Lloyd, M. J. Freedman, M. Kaminsky, and D. G. Andersen Do not Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS Best Paper Award, SOSP 2011 To know more: D. B. Terry, M. M. Theimer, K. Petersen, A. J. Demers, M. J. Spreitzer and C. H. Hauser Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System Best Paper Award, SOSP 1995 S. A. Mehdi, C. Littley, N. Crooks, N. Bronson, L. Alvisi, and W. Lloyd I Can't Believe It's Not Causal! Scalable Causal Consistency with No Slowdown Cascades C. Ding, D. Chu, E. Zhao, X. Li, L. Alvisi, and R. van Renesse Scalog: Seamless Reconfiguration and Total Order in a Scalable Shared Log
11/4, 11/6, 11/8	Randomized Consensus	Failure Detectors		HW 3 Out 11/8 Labs 4.1 due Lab 4.3 out	Class Notes To know more: M. Ben-Or. Another advantage of free choice: Completely Asynchronous Agreement Protocols E.W. Dijkstra Prize 2015. T. Chandra and S. Toueg. Unreliable Failure Detectors for Reliable Distributed Systems E.W. Dijkstra Prize 2010. T. Chandra, V. Hadzilakos, and S. Toueg. The Weakest Failure Detector for Solving Consensus E.W. Dijkstra Prize 2010.
11/11, 11/13, 11/15	Failure Detectors	Synchronous BFT		11/15: Lab 4.2 due Lab 4.3 design document due	Class Notes Required readings: J.B. Leners, H. Wu, W. Hung, M. Aguilera, M. Walfish. Detecting failures in distributed systems with the FALCON spy network
11/18, 11/20, 11/22	Synchronous BFT	Asynchronous BFT			Class Notes Required readings: M. Castro and B. Liskov Practical Byzantine Fault-Tolerance To know more: L. Lamport, R. Shostak, and M. Pease The Byzantine Generals Problem E.W. Dijkstra Prize, 2005.
11/25, 11/27, 11/29	Asynchronous BFT	Thanksgiving	Thanksgiving	11/25: HW 3 due	Class Notes Required readings: R. Kotla, L. Alvisi, M. Dahlin, A. Clement, and E.L. Wong Zyzzyva: Speculative Byzantine Fault Tolerance Best Paper Award, SOSP 2007 Y. Zhang, Q. Chen, L. Alvisi, S. Setty, and L. Zhou Byzantine Ordered Consensus without Byzantine Oligarchy Jay Lepreau Best Paper Award, OSDI 2020 To know more: M. Kapritsos, Y. Wang, V. Quema, A. Clement, L. Alvisi, and M. Dahlin All about Eve: Execute-Verify Replication for Multi-Core Servers
12/2, 12/4, 12/6	BFT and Blockchains	BFT and Blockchains			Class Notes Required reading: I. Abraham, L. Alvisi, and J. Halpern Distributed computing meets game theory: combining insights from two fields To know more: A.S. Ayer, A Clement, M. Dahlin, C. Porth, and L. Alvisi BAR Fault Tolerance for Cooperative Services Best Paper Award, SOSP 2005.
12/9, 12/11, 12/13	Distributed Computing meets Game Theory	The semester is over!	Hurrah!		Class Notes Required reading: I. Abraham, L. Alvisi, and J. Halpern Distributed computing meets game theory: combining insights from two fields To know more: A.S. Ayer, A Clement, M. Dahlin, C. Porth, and L. Alvisi BAR Fault Tolerance for Cooperative Services Best Paper Award, SOSP 2005.