Syllabus - Course Schedule

Week	Tuesday	Thursday	Assignment	Readings & Notes
1/18, 1/20	Intro-2 Generals Problem	Event Ordering and Global Predicate Detection		Week 0 Notes Recommended Reading: J. Halpern and Y. Moses Knowledge and Common Knowledge in a Distributed Environment E.W. Dijkstra Prize 2009.
1/25, 1/27	Lamport Clocks, Snapshot Protocol	Causal Order Vector Clocks		1/27: 255th 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 L. Lamport Time, Clocks, and the Ordering of Events in a Distributed System E.W. Dijkstra Prize 2000.
2/1, 2/3	Detecting non-stable properties	Atomic Commit		Week 2 Notes February 4th: Two additional hours of class to substitute for the classes of February 15/February 17 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/8, 2/10	3-Phase Commit Last Process to Fail	State Machine Replication	Homework 1 handed out Project 1 handed out	Week 3 Notes Required readings: F.B. Schneider The State Machine Approach
2/15, 2/17	Primary-backup	Rollback-Recovery	Homework 1 due	Week 4 Notes Required readings: T. Bressoud and F.B. Schneider Hypervisor-based Fault-Tolerance
2/22, 2/24	Rollback Recovery	Consensus and TRB - Crash	Project 1 due	Week 5 Notes Required readings: F.B. Schneider The State Machine Approach T. Bressoud and F.B. Schneider Hypervisor-based Fault-Tolerance
3/1, 3/3	Early stopping protocols	Consensus lower bounds		Week 6 Notes E. Elnozahy, L. Alvisi, Y.M.Wang, and D.B. Johnson A Survey of Rollback Recovery Protocols in Message Passing Systems
3/8, 3/10	Impossibility of Consensus	In-class midterm		Week 7 Notes Required readings: M.J. Fisher, N.A. Lynch, and M.S. Paterson Impossibility of Consensus E.W. Dijkstra Prize, 2001.
3/15, 3/17	Spring	Break
3/22, 3/24	Paxos	Circumventing FLP	Project 1 due Homework 2 handed out	Week 8 Notes Required readings: L. Lamport: Paxos Made Simple L. Lamport: The Part-Time Parliament T. Chandra: Paxos Made Live: An Engineering Perspective M. Ben-Or Another advantage of free choice: Completely Asynchronous Agreement Protocols
3/29, 3/31	Failure Detectors	Consistency and Replication	Homework 2 due	Week 9 Notes Required readings: T. Chandra and S. Toueg Unreliable Failure Detectors for Reliable Distributed Systems E.W. Dijkstra Prize, 2010. Recommended readings: A. Mostefaoui, S. Rajsbaum, and M. Raynal Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems T. Chandra, V. Hadzilakos, and S. Toueg The Weakest Failure Detector for Solving Consensus E.W. Dijkstra Prize, 2010.
4/5, 4/7	Bayou and Epidemic Protoocols	Quorum Systems		Week 10 Notes Required readings: 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. 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 D. Malkhi and M. Reiter Byzantine Quorum Systems Recommended readings: J.P. Martin, L. Alvisi, and M. Dahlin Minimal Byzantine Storage
4/12, 4/14	Leader Election	Clock Synchronization		Week 11 Notes Required readings: F. Cristian Probabilistic Clock Synchronization
4/19, 4/21	BFT: synchronous TRB	BFT: synchronous TRB	Project 2 due	Week 12 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
4/26, 4/28	Practical BFT	Practical BFT	Homework 3 handed out	Week 13 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
5/3, 5/5	Distributed Computing meets Game Theory	Review	Homework 3 due	Week 14 Notes Required readings: H.C. Li, A. Clement, E.L.Wong, J. Napper, L. Alvisi, and M. Dahlin. BAR Gossip H.C. Li, A. Clement, E.L.Wong, J. Napper, L. Alvisi, and M. Dahlin. Flightpath: Obedience vs. Choice in Cooperative Services