Course Schedule

Week	Tuesday	Thursday	Assignment	Readings & Notes
1/15, 1/17	Intro-2 Generals Problem	Event Ordering and Global Predicate Detection		Week 0 Notes (part 1) Week 0 Notes (part 2)
1/22, 1/24	Lamport Clocks, Snapshot Protocol	Causal Order Vector Clocks		NO CLASS THIS WEEK 1/27: 251th Anniversary of Mozart's birth 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
1/29, 1/31	Detecting non-stable properties	Atomic Commit		MAKE-UP CLASS: Friday 2/1, PAI 3.14, 2:00-5:00 PM Week 2 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
2/5, 2/7	3-Phase Commit Last Process to Fail	Intro to Fault-Tolerance Primary Backup	Project 1: Implement 3 phase atomic commit	Week 3 Notes
2/12, 2/14	Rollback Recovery	Rollback Recovery	Project 1 due Sunday 2/17 at 11:59pm	NO CLASS ON 2/12 Week 4 Notes Required readings: E. Elnozahy, L. Alvisi, Y.M.Wang, and D.B. Johnson A Survey of Rollback Recovery Protocols in Message Passing Systems F. Qin, J. Tucek, J. Sundaresan, and Y. Zhou Rx: Treating Bugs As Allergies-A Safe Method to Survive Software Failures
2/19, 2/21	State Machine Replication	Leader Election	Homework 1 handed out	Week 5.1 Notes Week 5.2 Notes Required readings: F.B. Schneider The State Machine Approach T. Bressoud and F.B. Schneider Hypervisor-based Fault-Tolerance
2/26, 2/28	Consensus Terminating Reliable Bcast Lower bounds	TRB for AFMA	Homework 1 due	Week 6 Notes (part 1) Week 6 Notes (part 2) Required readings: L. Lamport, R. Shostak, and M. Pease The Byzantine Generals Problem
3/4, 3/6	TRB for Arbitrary Failures	TRB for Arbitrary Failures	Homework 2 handed out	NO CLASS ON 3/6 Week 7 Notes Required readings: T.K. Srikanth and S. Toueg Simulating Authenticated Broadcast to Derive Simple Fault Tolerant Algorithms
3/11, 3/13	Spring	Break
3/18, 3/20	Impossibility of Consensus	Paxos	Homework 2 due Project 2: Implement State Machine Replication in Paxos	Week 8 Notes Required readings: M.J. Fisher, N.A. Lynch, and M.S. Paterson Impossibility of Consensus L. Lamport: Paxos Made Simple L. Lamport: The Part-Time Parliament
3/25, 3/27	Circumventing FLP	Failure Detectors	Project 2 due	Week 9 Notes Required readings: M. Ben-Or Another advantage of free choice: Completely Asynchronous Agreement Protocols T. Chandra and S. Toueg Unreliable Failure Detectors for Reliable Distributed Systems Recommended readings: A. Mostefaoui, S. Rajsbaum, and M. Raynal Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems Chandra, Hadzilakos, and Toueg The Weakest Failure Detector for Solving Consensus
4/1, 4/3	Clock Synchronization	From Paxos to Practical BFT	Project 3 handed out (tentative date)	Week 10 Notes Required readings: H. Li, A. Clement, A.S. Aiyer, and L. Alvisi The Paxos Register M. Castro and B. Liskov Practical 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
4/8, 4/10	Practical BFT	Practical BFT	Paper review handed out	Week 11 Notes Required readings: D. Malkhi and M. Reiter Byzantine Quorum Systems R. Kotla, L. Alvisi, M. Dahlin, A. Clement, and E.L. Wong Zyzzyva: Speculative Byzantine Fault Tolerance Recommended readings: J.P. Martin, L. Alvisi, and M. Dahlin Minimal Byzantine Storage
4/15, 4/27	Beyond PBFT	Epidemic protocols	Paper review due	Week 12 Notes Required readings: A. Clement, H. Li, J. Napper, J.P. Martin, L. Alvisi, and M. Dahlin. BAR Primer A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry. Epidemic algorithms for replicated database maintenance. K.P. Birman, M. Hayden, O. Ozkasap, Z. Xiao, M. Budiu, and Y. Minsky. Bimodal Multicast. Recommended readings: P. Th. Eugster, R. Guerraoui, S.B. Handurukande, P. Kouznetsov, A.-M. Kermarrec. Lightweight Probabilistic Broadcast. 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, 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 D.B. Terry, A.J. Demers, K. Petersen, M.J. Spetzer, M.M. Theimer, B.B. Welch. Session Guarantees for Weakly Consistent Replicated Data H.C. Li, A. Clement, E.L.Wong, J. Napper, L. Alvisi, and M. Dahlin. BAR Gossip
4/22, 4/24	Shared Memory	Shared Memory	Homework 3 handed out Project 3 due	Week 13 Notes (BAR) Week 13 Notes (Topology) Required readings: M. Herlihy Wait-free Synchronization M. Herlihy A Methodology for Implementing Highly Concurrent Data Objects P. Jayanti On the robustness of Herlihy's hierarchy
4/29, 5/1	Shared Memory	Shared Memory	Homework 3 due	Week 14 Notes