Course Schedule

Week	Monday	Wednesday	Friday	Assignment	Readings & Notes
9/2, 9/4, 9/6	Labor Day	Intro-2 Generals Problem			Week 0 Notes 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.
9/9, 9/11, 9/13	Event Ordering and Global Predicate Detection	Lamport Clocks, Snapshot Protocol			Week 1 Notes Required readings: O. Babaoglu and K. Marzullo Consistent Global States of Distributed Systems Recommended readings: 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/16, 9/18, 9/20	Causal Order Vector Clocks	Detecting non-stable properties			Week 2 Notes
9/23, 9/25, 9/27	Atomic Commit	3-Phase Commit Last Process to Fail	State Machine Replication		Week 3 Notes Required readings: Bernstein, Goodman and Hadzilakos Distributed Recovery Recommended readings: D. Skeen Non-blocking Commit Protocols D. Skeen Determining the Last Process to Fail
9/30, 10/2, 10/4		Primary-backup			Week 4 Notes Required readings: F.B. Schneider The State Machine Approach SIGOPS Hall of Fame T. Bressoud and F.B. Schneider Hypervisor-based Fault-Tolerance Recommended readings: R. van Renesse and F.B. Schneider Chain Replication for Supporting High Throughput and Availability
10/7, 10/9, 10/11	Logging and Rollback Recovery	Logging Rollback Recovery			Week 5 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 Recommended readings: E. Elnozahy, L. Alvisi, Y.M.Wang, and D.B. Johnson A Survey of Rollback Recovery Protocols in Message Passing Systems
10/14, 10/16, 10/18	Fall break	Consensus and TRB Consensus lower bounds	FLP		Week 6 Notes Required readings: Fisher, Lynch, Paterson. Impossibility of Consensus E.W.Dijkstra Prize, 2001.
10/21, 10/23, 10/25	Midterm	Paxos			Week 7 Notes Required readings: Fisher, Lynch, Paterson. Impossibility of Consensus E.W.Dijkstra Prize, 2001.
10/28, 10/30, 11/1	Away	Away	Paxos		Week 8 Notes Required readings: L. Lamport. Paxos Made Simple L. Lamport. The Part-Time Parliament SIGOS Hall of Fame R. van Renesse. Paxos made moderately complex
11/4, 11/6, 11/8	Circumventing FLP: Ben Or	Failure detectors			Week 9 Notes Required readings: T. Chandra and S. Toueg. Unreliable Failure Detectors for Reliable Distributed Systems E.W. Dijkstra Prize 2010. J.B. Leners, H. Wu, W. Hung, M. Aguilera, M. Walfish. Detecting failures in distributed systems with the FALCON spy network Recommended readings: T. Chandra, V. Hadzilakos, and S. Toueg. The Weakest Failure Detector for Solving Consensus E.W. Dijkstra Prize 2010. M. Ben-Or. Another advantage of free choice: Completely Asynchronous Agreement Protocols E.W. Dijkstra Prize 2015. Mahesh Balakrishnan, Dahlia Malkhi, Vijayan Prabhakaran, Ted Wobber, Michael Weiss, John D. Davis Corfu: A Distributed Shared Log
11/11, 11/13, 11/15	Consistency models: Linearizability Serializability Eventual Consistency	Epidemic protocols Bayou Causal Consistency	Causal consistency		Week 10 Notes Recommended readings: 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 K. Petersen, M. J. Spreitzer, D. B. Terry, M. M. Theimer and A. J. Demers. Flexible Update Propagation for Weakly Consistent Replication D.B. Terry, A.J. Demers, K. Petersen, M.J. Spetzer, M.M. Theimer, B.B. Welch. Session Guarantees for Weakly Consistent Replicated Data
11/18, 11/20, 11/22	AWAY	Quorum systems From NoSQL to NewSQL	FLP Thurston 205 1:15pm--2:45pm		Week 11 Notes Required readings: Wyatt Lloyd, Michael J. Freedman, Michael Kaminsky, and David G. Andersen Don't Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS Recommended readings: G. DeCandia et al. Dynamo: Amazon's Highly Available Key-value Store C. Li, D. Porto, A. Clement, et al. Making Geo-Replciated Systems Fast As Possible, Consistent When Necessary
11/25, 11/27, 11/29	Clock Synchronization	Thanksgiving	Thanksgiving		Week 12/13 Notes Recommended readings: F. Cristian Probabilistic Colck Synchronization Dahlia Malkhi and Mike Reiter Byzantine Quorum Systems Maurice Herlihy A Quorum-Consensus Replication Method for Abstract Data Types
12/2, 12/4, 12/6	Synchronous BFT	Asynchronous BFT			Week 13 Notes Recommended readings: L. Lamport, R. Shostak, and M. Pease The Byzantine Generals Problem E.W. Dijkstra Prize, 2005. T.K. Srikanth and S. Toueg Simulating Authenticated Broadcast to Derive Simple Fault Tolerant Algorithms
12/9	Asynchronous BFT	Final Review (Optional)			Week 14 Notes Required readings: M. Castro and B. Liskov Practical Byzantine Fault-Tolerance Recommended readings: R. Kotla, L. Alvisi, M. Dahlin, A. Clement, and E.L. Wong Zyzzyva: Speculative Byzantine Fault Tolerance