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 Tuesday/Thursday 3:20pm PT, or anytime on YouTube!

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

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); properties of executions; delivery vs. receiving; 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: uses of causality in distributed systems; implementing causal broadcast; consistent snapshots; Chandy-Lamport snapshot algorithm; Chandy-Lamport limitations, assumptions, properties  
Thursday, 4/15 Lecture 6: centralized vs. decentralized algorithms; recap of delivery guarantees and protocols; safety and liveness; reliable delivery  
Tuesday, 4/20 Lecture 7: fault classification and fault models; two generals problem; implementing reliable delivery; idempotence; at-least-once/at-most-once/exactly-once delivery  
Thursday, 4/22 Lecture 8: unicast/broadcast/multicast; reliable broadcast; implementing reliable broadcast; intro to replication; total order vs. determinism; consistency models: FIFO, causal, “strong”  
Friday, 4/23   Programming assignment 2 due
Tuesday, 4/27 Lecture 9: 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: midterm recap; handling node failure in replication protocols; introduction to consensus; problems equivalent to consensus; the FLP result Mid-course survey out
Thursday, 5/6 Lecture 11: introduction to Paxos; Paxos: the interesting parts  
Friday, 5/7   Mid-course survey due
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  
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  
Tuesday, 5/18 Lecture 14: 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 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 (TBA)  
Thursday, 5/27 Lecture 16: 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, 6/1 Lecture 17: MapReduce: types, approach to fault tolerance, combine functions, more examples  
Thursday, 6/3 Lecture 18: the math behind replica conflict resolution: recap of strong convergence; recap of partial orders; upper bounds, least upper bounds, join-semilattices; final exam review and AMA  
Friday, 6/4   Programming assignment 4 due
Thursday, 6/10 Final exam (covering lectures 1-18), noon-3pm Pacific time