This schedule is tentative, and it is neither sound (i.e., if something’s listed here, that doesn’t mean we’ll cover it) nor complete (i.e., if something’s 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
Friday, 9/24 Lecture 1: logistics/administrivia/expectations; distributed systems: what and why? Start-of-course survey out
Monday, 9/27 Lecture 2: more logistics/administrivia/expectations; time and clocks; Lamport diagrams; causality and happens-before; network models  
Wednesday, 9/29 Lecture 3: state and events; recap of happens-before; partial orders and total orders; Lamport clocks Start-of-course survey due; programming assignment 1 out
Friday, 10/1 Lecture 4: Lamport clocks recap; vector clocks  
Monday, 10/4 Lecture 5: delivery vs. receiving; properties of executions: FIFO delivery, causal delivery, totally-ordered delivery; implementing FIFO delivery; unicast/broadcast/multicast  
Wednesday, 10/6 Lecture 6: implementing causal broadcast; introduction to distributed snapshots; preview of Chandy-Lamport snapshot algorithm Programming assignment 1 due; programming assignment 2 out
Friday, 10/8 Lecture 7: causal broadcast wrap-up; introduction to Chandy-Lamport snapshot algorithm  
Monday, 10/11 Lecture 8: more on Chandy-Lamport; Chandy-Lamport limitations, assumptions, properties; centralized vs. decentralized algorithms  
Wednesday, 10/13 Lecture 9: Chandy-Lamport wrap-up; recap of centralized vs. decentralized algorithms; fault classification and fault models  
Friday, 10/15 Lecture 10: recap of fault classification and fault models; two generals problem; implementing reliable delivery  
Monday, 10/18 Lecture 11: idempotence; so-called “exactly-once” delivery; reliable broadcast; implementing reliable broadcast; preview of replication  
Wednesday, 10/20 Lecture 12: reasons to do replication; total order vs. determinism; strong consistency (informally); primary-backup replication; chain replication; latency and throughput Programming assignment 2 due
Friday, 10/22 Lecture 13: handling node failure in replication protocols; consistency models (read-your-writes, FIFO, causal, strong)  
Monday, 10/25 Midterm exam (covering lectures 1-13)  
Wednesday, 10/27 Lecture 14: post-midterm review; introduction to consensus; problems equivalent to consensus; the FLP result Programming assignment 3 out
Friday, 10/29 Lecture 15: introduction to Paxos  
Monday, 11/1 Lecture 16: More on Paxos; Multi-Paxos  
Wednesday, 11/3 Lecture 17: Paxos wrap-up; other consensus protocols; eventual consistency; network partitions; availability; the consistency/availability trade-off Mid-course survey out
Friday, 11/5 Lecture 18: Dynamo; intro to: application-specific conflict resolution; anti-entropy with Merkle trees, gossip Reading assignment 1: read “Dynamo: Amazon’s Highly Available Key-value Store” for class today
Monday, 11/8 Lecture 19: Dynamo, continued: quorum systems; tail latency; introduction to sharding Mid-course survey due
Wednesday, 11/10 Lecture 20: more about sharding; consistent hashing  
Friday, 11/12 Lecture 21: 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
Monday, 11/15 Recent grads panel: Aria Diamond, Lawrence Lawson, Timothy Nguyen, Matthew Rhea, Melanie Wong  
Wednesday, 11/17 HACK DAY (no lecture) Programming assignment 3 due; programming assignment 4 out on Thursday, 11/18
Friday, 11/19 Lecture 22: MapReduce: approach to fault tolerance; combine functions; more examples  
Monday, 11/22 Guest speaker: Mae Milano  
Wednesday, 11/24 Lecture 23: strong convergence and strong eventual consistency; the math behind replica conflict resolution: recap of partial orders; upper bounds, least upper bounds, join-semilattices  
Friday, 11/26 No class (Thanksgiving)  
Monday, 11/29 Guest speaker: Maggie Zhou  
Wednesday, 12/1 Lecture 24: tying up loose ends: revisiting physical clocks; revisiting fault tolerance; passive vs. active (state machine) replication  
Friday, 12/3 Final exam review and AMA Programming assignment 4 due
Wednesday, 12/8 Final exam (covering lectures 1-24), noon-3pm Pacific time