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). Assignments are due at 11:59:59pm on the listed due date unless otherwise specified.

You can watch lectures live on Twitch Tuesday/Thursday 3:20pm PT, or anytime on YouTube!

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