Schedule of topics

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).

You can watch lectures live on Twitch Monday/Wednesday/Friday at 9:20am PDT, or anytime on YouTube!

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

Date Topics Notes
Monday, 3/30 Lecture 1: logistics/administrivia/expectations  
Wednesday, 4/1 Lecture 2: distributed systems: what and why?; time and clocks  
Friday, 4/3 Lecture 3: Lamport diagrams; causality and happens-before; network models; state and events; partial orders Programming assignment 1 out
Monday, 4/6 Lecture 4: recap of partial orders; total orders; recap of happens-before; Lamport clocks  
Wednesday, 4/8 Lecture 5: vector clocks; protocol runs and anomalies; delivery vs. receiving; FIFO delivery  
Friday, 4/10 Lecture 6: recap of delivery vs. receiving; recap of FIFO delivery; causal delivery; totally-ordered delivery; implementing FIFO delivery; preview of implementing causal broadcast Programming assignment 1 due; programming assignment 2 out
Monday, 4/13 Lecture 7: implementing causal broadcast; uses of causality in distributed systems; consistent snapshots; preview of Chandy-Lamport snapshot algorithm  
Wednesday, 4/15 Lecture 8: Chandy-Lamport snapshot algorithm  
Friday, 4/17 Lecture 9: Chandy-Lamport wrap-up: limitations, assumptions, properties; uses of snapshots; centralized vs. decentralized algorithms; recap of delivery guarantees and protocols; safety and liveness Last day to add/drop/swap courses
Monday, 4/20 Lecture 10: recap of safety and liveness; reliable delivery; fault classification and fault models; two generals problem  
Wednesday, 4/22 Lecture 11: implementing reliable delivery; idempotence; at-least-once/at-most-once/exactly-once delivery; unicast/broadcast/multicast; reliable broadcast; implementing reliable broadcast; preview of replication  
Friday, 4/24 Lecture 12: replication; total order vs. determinism; consistency models: FIFO, causal, “strong”; primary-backup replication; chain replication; latency and throughput Programming assignment 2 due
Monday, 4/27 Lecture 13: *pause for breath*  
Wednesday, 4/29 Midterm exam  
Friday, 5/1 Lecture 14: handling node failure in replication protocols; introduction to consensus; problems equivalent to consensus; the FLP result; introduction to Paxos Programming assignment 3 out
Monday, 5/4 Lecture 15: Paxos: the interesting parts  
Wednesday, 5/6 Lecture 16: Paxos wrap-up: nontermination, Multi-Paxos, fault tolerance; other consensus protocols: Viewstamped Replication, Zab, Raft; passive vs. active (state machine) replication  
Friday, 5/8 Lecture 17: eventual consistency; strong convergence and strong eventual consistency; intro to application-specific conflict resolution; network partitions; availability; the consistency/availability trade-off  
Monday, 5/11 Lecture 18: Dynamo: review of old ideas (availability, network partitions, eventual consistency, vector clocks, application-specific conflict resolution); intro to: anti-entropy with Merkle trees, gossip, quorum consistency Read “Dynamo: Amazon’s Highly Available Key-value Store” for class today
Wednesday, 5/13 Lecture 19: more about quorum consistency; introduction to sharding; consistent hashing  
Friday, 5/15 Recent grads panel: Emma Gomish, Lawrence Lawson, Victoria Tran, Pete Wilcox  
Monday, 5/18 Lecture 20: online systems vs. offline systems, raw data vs. derived data; intro to MapReduce; MapReduce example: forward index to inverted index Read “MapReduce: Simplified Data Processing on Large Clusters” for class today
Wednesday, 5/20 Lecture 21: MapReduce: types, approach to fault tolerance, combine functions, more examples  
Friday, 5/22 HACK DAY (no lecture) Programming assignment 3 due; programming assignment 4 out
Monday, 5/25 No class (Memorial Day)  
Wednesday, 5/27 Guest speaker: Chris Colohan (ex-Google; distributedsystemscourse.com)  
Friday, 5/29 Lecture 22: the math behind replica conflict resolution: recap of strong convergence; recap of partial orders; upper bounds, least upper bounds, join-semilattices  
Monday, 6/1 Lecture 23: research topic: domain-specific solvers for distributed consistency  
Wednesday, 6/3 Guest speaker: Karissa McKelvey (Digital Democracy)  
Friday, 6/5 Final exam review and AMA Programming assignment 4 due
Tuesday, 6/9 Final exam, 4:00–7:00 p.m.