Course Schedule

Week	Monday	Wednesday	Friday	Assignment	Readings & Notes
8/23, 8/25		Intro-2 Generals Problem			Week 0 Notes Recommended readings: J. Halpern and Y. Moses Knowledge and Common Knowledge in a Distributed Environment E.W. Dijkstra Prize 2009.
8/28, 8/30, 1/9	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/4, 9/6, 9/8	Labor Day	Causal Order Vector Clocks			Week 2 Notes
9/11, 9/13, 9/15	Detecting non-stable properties	Atomic Commit	3-Phase Commit Last Process to Fail		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/18, 9/20, 9/22	State Machine Replication	Primary-backup	Possible catch-up class		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
9/25, 9/27, 9/29	Logging and Rollback Recovery	Logging Rollabck Recovery	Homework discussion		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/2, 10/4, 10/6	Consensus and TRB Consensus lower bounds	FLP	Regular class		Week 6 Notes Required readings: Fisher, Lynch, Paterson. Impossibility of Consensus E.W.Dijkstra Prize, 2001.
10/9, 10/11, 10/13	Fall break	Regular class	Review Session		Week 7 Notes
10/16, 10/18, 10/20	Midterm	Paxos	Midterm discussion		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
10/23, 10/25, 10/27	Paxos Corfu	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
10/30, 11/1, 11/3			Consistency models: Linearizability Serializability Eventual 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/6, 11/8, 11/10	Epidemic protocols Bayou Causal Consistency		Causal Consistency		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/13, 11/15, 11/17	Quorum systems From NoSQL to NewSQL		Clock Synchronization		Week 12 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
11/20, 11/22, 11/24	Synchronous BFT	Thanksgiving	Thanksgiving		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
11/27, 11/29, 12/1	Asynchronous BFT	Asynchronous BFT	Final Review		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