Course Schedule

Week	Monday	Wednesday	Friday	Assignment	Readings & Notes
8/27, 8/29	Intro-2 Generals Problem	Event Ordering and Global Predicate Detection			Week 1 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/3, 9/5, 9/7	Labor Day	Lamport Clocks, Snapshot Protocol			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/10, 9/12, 9/14	Causal Order Vector Clocks	Detecting non-stable properties			Week 2 and 3 Notes
9/17, 9/19, 9/21	Atomic Commit	3-Phase Commit Last Process to Fail			Week 4 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/24, 9/26, 9/28	State Machine Replication	Primary-backup			Week 5 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/1, 10/3, 10/5	Logging and Rollback Recovery	Logging Rollabck Recovery			Week 6 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/8, 10/10, 10/12	Fall break	Midterm			Required readings: Fisher, Lynch, Paterson. Impossibility of Consensus E.W.Dijkstra Prize, 2001.
10/15, 10/17, 10/19	Consensus and TRB Consensus lower bounds	FLP			Week 7 Notes Required readings: Fisher, Lynch, Paterson. Impossibility of Consensus E.W.Dijkstra Prize, 2001.
10/22, 10/24, 10/26	Paxos	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
10/29, 10/31, 11/2	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/5, 11/7, 11/9	Consistency models: Linearizability Serializability Eventual Consistency	Epidemic protocols Bayou 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/12, 11/14, 11/16	Causal Consistency	Quorum systems From NoSQL to NewSQL			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/19, 11/21, 11/23	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
11/26, 11/28, 11/30	Synchronous BFT	Asynchronous BFT			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/3	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