Tentative Course Schedule

Week	Monday	Wednesday	Friday	Assignment	Readings & Notes
1/23, 1/25, 1/27	No Class	No CLass			Required readings: E. Michael et al. Teaching Rigorous Distributed Systems with Efficient Model Checking
1/30, 2/1, 2/3	Intro-2 Generals Problem	Event Ordering and Global Predicate Detection	Lab 0/1 Intro (Zoom)	Lab assignments are accessible through CMS Labs 0/1 out	Class Notes Notes and video from Friday's lecture Required readings: 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. O. Babaoglu and K. Marzullo Consistent Global States of Distributed Systems Chapter 4 of Sape Mullender's Distributed Systems, 2nd Edition.
2/6, 2/8, 2/10	Lamport Clocks, Snapshot Protocol	Causal Order, Vector Clocks	Detecting non-stable properties	Lab 1 due HW 1 Out	Class Notes for Monday and Wednesday Class Notes and video for Friday 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.
2/13, 2/15, 2/17	State Machine Replication	Primary Backup	Lab 2 Intro	Lab 2 out HW 1 due	Class Notes Class Notes and video for Friday 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
2/20, 2/22, 2/24	Logging and Rollback Recovery	Logging and Rollback Recovery	Consensus and TRB Consensus lower bounds		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: E. Elnozahy, L. Alvisi, Y. M.Wang, and D. B. Johnson A Survey of Rollback Recovery Protocols in Message Passing Systems
2/27, 3/1, 3/3	February Break	FLP	Consensus and TRB Consensus lower bounds	Lab 2 due HW 2 Out	Class Notes for the week in-class and recorded lectures Video for Friday lecture Video for Make-up lecture (Part I) Video for Make-up lecture (Part II) To know more: M. Fisher, N. Lynch, M. Paterson Impossibility of Consensus E.W.Dijkstra Prize, 2001.
3/6, 3/8, 3/10	Beyond FLP	Paxos	Lab 3 Intro	Lab 3 out HW2 due	Class Notes Video and notes for Friday lecture 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
3/13, 3/15, 3/17	Atomic Commit	3-Phase Commit Last Process to Fail	Consistency		Class Notes Video for Friday lecture 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
3/20, 3/22, 3/24	Midterm	Spanner	Intro to Lab 4.1		Class Notes Required readings: J.C. Corbett et al Spanner: Google's Globally Distributed Database
3/27, 3/29, 3/31	Weakly consistent systems	The Log Abstraction	Intro to Lab 4.1	Lab 3 due Lab 4.1 out	Class Notes Video and notes for Friday lecture Required readings: 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 Don't Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS Best Paper Award, SOSP 2011 M. Balakrishnan, D. Malkhi, J.D. Davis, V. Prabhakaran, M. Wei, and T. Wobber Corfu: A Distributed Shared Log 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
4/3, 4/5, 4/7	Spring Break	Spring Break	Spring Break
4/10, 4/12, 4/14	Randomized Consensus	Failure Detectors	Intro to Lab 4.2 and Lab 4.3	HW3 Out Labs 4.2 and 4.3 out Lab 4.1 due	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.
4/17, 4/19, 4/21	Failure Detectors	Synchronous BFT		HW3 due	Class Notes Notes and video for Labs 4.2 and 4.3. Required readings: J.B. Leners, H. Wu, W. Hung, M. Aguilera, M. Walfish. Detecting failures in distributed systems with the FALCON spy network
4/24, 4/26, 4/28	Synchronous BFT	NO CLASS TODAY		Lab 4.2 due	Class Notes Video for Friday's make up lecture 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.
5/1, 5/3, 5/5	Asynchronous BFT	BFT and Blockchains		Lab 4.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, 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, M. Dahlin All about Eve: Execute-Verify Replication for Multi-Core Servers
5/8, 5/10, 5/12	Distributed Computing meets Game Theory	The semester is over!	Hurrah!		Class Notes Review Session 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.