CSE 223A: Principles of Distributed Computing
Winter 2009

Keith Marzullo
CSE 2266
marzullo@cs.ucsd.edu

Class meets Tuesdays and Thursdays 2:00-3:20 PM in HSS 2305A

Reference texts:

Homework here.

Project here.

Schedule:

date topic notes reading
1/6 Introduction pdf  
1/8 Properties. Global states, consistent cuts, logical clocks. pdf Consistent Global States of Distributed Systems: Fundamental Concepts and Mechanisms
Distributed Snapshots: Determining Global States of Distributed Systems
1/13 (continued) pdf  
1/15 Vector clocks. pdf Efficient detection of a class of stable properties
1/20 Quorums pdf Weighted voting for replicated data
How to Assign Votes in a Distributed System (deep paper; use as reference.)
A Sqrt(N) Algorithm for Mutual Exclusion in Decentralized Systems
1/22 Quorums (continued)    
1/27 State Machine replication pdf The State Machine Approach: A Tutorial
1/29 Rollback recovery pdf A Survey of Rollback-Recovery Protocols in Message-Passing Systems
2/3 Atomic commit pdf Distributed Recovery
2/5 Last Process to Fail
Introduction to Consensus		 pdf
pdf		 Reaching Agreement in the Presence of Faults
2/10 Consensus on redundant busses pdf Synchronous Atomic Broadcast for Redundant Broadcast Channels
Streets of Byzantium: Network Architectures for Fast Reliable Multicast
2/12 Translation pdf Simulating authenticated broadcasts to derive simple fault-tolerant algorithms
2/17 Impossibility of Consensus pdf Impossibility of Distributed Consensus with One Faulty Process
2/19 Failure detectors pdf Unreliable Failure Detectors for Reliable Distributed Systems
2/24 Paxos pdf The Part-Time Parliament
Paxos Made Simple
2/26 Riffs on Paxos pdf Fast Paxos
Consensus on Transaction Commit
3/3 (Continued: Fast Paxos, Atomic Commit Paxos) pdf  
3/5 Wide-area consensus
Guest lecturer: Yanhua Mao		 pdf Classic Paxos vs. Fast Paxos: caveat emptor
Mencius: Building Efficient Replicated State Machines for WANs
3/10 BFT pdf Practical Byzantine Fault Tolerance and Proactive Recovery
Fast Byzantine Consensus
3/12 Riffs on BFT    

Last edited 7 February 2009