Syllabus - 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 Recommended Reading: J. Halpern and Y. Moses Knowledge and Common Knowledge in a Distributed Environment E.W. Dijkstra Prize 2009.
1/22, 1/24	Lamport Clocks, Snapshot Protocol	Causal Order Vector Clocks		1/27: 257th 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.
1/29, 1/31	Detecting non-stable properties	Atomic Commit		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	State Machine Replication	Homework 1 handed out on 2/7 Due 2/14	Week 3 Notes Required readings: F.B. Schneider The State Machine Approach
2/12, 2/14	Primary-backup	Rollback-Recovery	Homework 1 due	Week 4 Notes Required readings: T. Bressoud and F.B. Schneider Hypervisor-based Fault-Tolerance
2/19, 2/21	Rollback Recovery	Consensus and TRB - Crash		Week 5 Notes E. Elnozahy, L. Alvisi, Y.M.Wang, and D.B. Johnson A Survey of Rollback Recovery Protocols in Message Passing Systems
2/26, 2/28	Early stopping protocols	Consensus lower bounds		Week 6 Notes
3/5, 3/7	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/12, 3/14	Spring	Break
3/19, 3/21	Paxos	Circumventing FLP	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/26, 3/28	Failure Detectors	Consistency and Replication	Homework 2 due Project 1 handed out	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/2, 4/4	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 Recommended readings: D. Malkhi and M. Reiter Byzantine Quorum Systems J.P. Martin, L. Alvisi, and M. Dahlin Minimal Byzantine Storage
4/9, 4/11	Leader Election	Clock Synchronization	Project 1 due 4/12	Week 11 Notes Required readings: F. Cristian Probabilistic Clock Synchronization
4/16, 4/18	BFT: synchronous TRB	BFT: synchronous TRB	Project 2	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/23, 4/25	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
4/30, 5/2	Distributed Computing meets Game Theory	Review	Project 2 due 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