Course Schedule

Week	Monday	Wednesday	Friday	Assignment	Readings & Notes
22/8, 24/8/ 26/8		Intro-2 Generals Problem			Week 0 Notes Required readings: J. Halpern and Y. Moses Knowledge and Common Knowledge in a Distributed Environment E.W. Dijkstra Prize 2009.
29/8, 31/8, 9/2	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/5, 9/7, 9/9	Labor Day	Causal Order Vector Clocks	Causal Order Vector Clocks		Week 2 Notes
9/12, 9/14, 9/16	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/19, 9/21, 9/23	State Machine Replication	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
9/26 9/28, 9/30	Logging and Rollback Recovery	Logging Rollabck Recovery			Week 5 Notes Required readings: E. Elnozahy, L. Alvisi, Y.M.Wang, and D.B. Johnson A Survey of Rollback Recovery Protocols in Message Passing Systems Recommended 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
10/3, 10/5, 10/7	Consensus and TRB Consensus lower bounds				Week 6 Notes
10/10, 10/12/ 10/14	Fall break	Review Session	Paxos		Week 7 Notes Review Session Notes Required readings: Fisher, Lynch, Paterson. Impossibility of Consensus E.W.Dijkstra Prize, 2001.
10/17, 10/19, 10/21	Midterm	Paxos	Review of the midterm		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 Mahesh Balakrishnan, Dahlia Malkhi, Vijayan Prabhakaran, Ted Wobber, Michael Weiss, John D. Davis Corfu: A Distributed Shared Log
10/24, 10/26, 10/28	Impossibility of Consensus	Circumventing FLP	Failure detectors		Week 9 Notes Required readings: T. Chandra and S. Toueg. Unreliable Failure Detectors for Reliable Distributed Systems E.W. Dijkstra Prize 2010. 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.
10/31, 11/2, 11/4	Consistency guarantees				Week 10 Notes Required 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 Recommended readings: 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/7, 11/9, 11/11	Bayou and Epidemic protocols	Relaxed consistency	From NoSQL to NewSQL		Week 11 Notes Required readings: G. DeCandia et al. Dynamo: Amazon's Highly Available Key-value Store Recommended readings: C. Li, D. Porto, A. Clement, et al. Making Geo-Replciated Systems Fast As Possible, Consistent When Necessary 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
11/14, 11/16/, 11/18	Clock Synchronization	Quorum Systems			Week 12 Notes Required readings: F. Cristian Probabilistic Colck Synchronization Dahlia Malkhi and Mike Reiter Byzantine Quorum Systems Recommended readings: Maurice Herlihy A Quorum-Consensus Replication Method for Abstract Data Types
11/21, 11/23, 11/25	Synchronous BFT	Thanksgiving	Thanksgiving		Week 13 Notes Required 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/28, 11/30, 12/2	Asynchronous BFT	Asynchronous BFT	Final Review		Week 14 Notes Required readings: M. Castro and B. Liskov Practical Byzantine Fault-Tolerance R. Kotla, L. Alvisi, M. Dahlin, A. Clement, and E.L. Wong Zyzzyva: Speculative Byzantine Fault Tolerance Recommended readings: J. Yin, J.P. Martin, A. Venkataramani, L. Alvisi, and M. Dahlin Separating Agreement from Execution for Byzantine Fault-Tolerant Services