This schedule is tentative, and it is neither sound (that is, if a particular reading or topic is listed here, that doesn’t mean we’ll cover it!) nor complete (that is, if a particular reading or topic is not listed here, that doesn’t mean we won’t cover it!).

Assignments are due at 11:59:59pm on the listed due date unless otherwise specified.

Date Topics Notes
Tuesday, 1/9 Lecture 1: logistics/administrivia/expectations; distributed systems: what and why? Start-of-course survey out
Thursday, 1/11 Lecture 2: time and clocks; Lamport diagrams; causality and happens-before; network models; state and events  
Friday, 1/12   Start-of-course survey due; programming assignment 1 out
Tuesday, 1/16 Lecture 3: happens-before recap; partial orders; total orders; Lamport clocks; vector clocks  
Thursday, 1/18 Lecture 4: Lamport clocks recap; vector clocks (continued); delivery vs. receiving; some safety properties of executions: FIFO delivery, causal delivery; implementing FIFO delivery  
Friday, 1/19   Programming assignment 1 due; programming assignment 2 out
Tuesday, 1/23 Lecture 5: recap of FIFO/causal delivery; totally-ordered delivery; unicast/broadcast/multicast; implementing causal broadcast; introduction to distributed snapshots  
Thursday, 1/25 Lecture 6: Chandy-Lamport snapshot algorithm  
Tuesday, 1/30 Lecture 7: Chandy-Lamport wrap-up; centralized vs. decentralized algorithms; safety and liveness; reliable delivery  
Thursday, 2/1 Lecture 8: fault classification and fault models; two generals problem; common knowledge; forms of fault tolerance; idempotence and “exactly-once” delivery  
Friday, 2/2   Programming assignment 2 due
Tuesday, 2/6 Lecture 9: reliable broadcast; implementing reliable broadcast; reasons to do replication; strong consistency (informally); midterm review  
Thursday, 2/8 Midterm exam (covering lectures 1-9)  
Friday, 2/9   Programming assignment 3 out
Tuesday, 2/13 Lecture 10: exam review; total order vs. determinism; consistency models (read-your-writes, FIFO, causal, strong); primary-backup replication  
Thursday, 2/15 Lecture 11: chain replication; latency and throughput; dealing with failure in strongly consistent replication protocols; intro to consensus; the FLP result Mid-course survey out
Tuesday, 2/20 Lecture 12: the Paxos protocol Mid-course survey due
Thursday, 2/22 Lecture 13: Paxos wrap-up: nontermination, Multi-Paxos, fault tolerance of Paxos  
Tuesday, 2/27 Lecture 14: brief discussion of other consensus protocols; passive vs. active (state machine) replication; eventual consistency; strong convergence and strong eventual consistency; intro to application-specific conflict resolution; network partitions  
Thursday, 2/29 Lecture 15: Dynamo concepts: availability and the consistency/availability trade-off; anti-entropy with Merkle trees; gossip; quorum consistency Reading assignment 1: read “Dynamo: Amazon’s Highly Available Key-value Store” for class today
Friday, 3/1   Programming assignment 3 due; programming assignment 4 out
Tuesday, 3/5 Lecture 16: introduction to sharding; consistent hashing  
Thursday, 3/7 Lecture 17: online systems vs. offline systems, raw data vs. derived data; intro to MapReduce; MapReduce example: forward index to inverted index Reading assignment 2: read “MapReduce: Simplified Data Processing on Large Clusters” for class today
Tuesday, 3/12 Lecture 18: MapReduce wrap-up; the math behind replica conflict resolution: recap of strong convergence; recap of partial orders; upper bounds, least upper bounds, join-semilattices  
Thursday, 3/14 Lecture 19: ask me anything  
Friday, 3/15   Programming assignment 4 due
Monday, 3/18 Final exam (covering lectures 1-18), 4-7pm Pacific time