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.

Date Topics Notes
Monday, 4/1 Lecture 1: logistics/administrivia/expectations; distributed systems: what and why?  
Wednesday, 4/3 Lecture 2: time and clocks; Lamport diagrams; causality and happens-before; network models; state and events  
Friday, 4/5 Lecture 3: happens-before recap; strict and non-strict partial orders; total orders; Lamport clocks Programming assignment 1 out
Monday, 4/8 Lecture 4: Lamport clocks recap; vector clocks; protocol runs and anomalies  
Wednesday, 4/10 Class cancelled due to campus labor strike  
Friday, 4/12 Guest lecture: Owen Arden Programming assignment 1 due; programming assignment 2A out
Monday, 4/15 Lecture 5: delivery vs. receiving; delivery guarantees: FIFO delivery, causal delivery, totally-ordered delivery; implementing FIFO delivery; preview of implementing causal delivery  
Wednesday, 4/17 Lecture 6: implementing causal delivery; uses of causality in distributed systems; cuts and consistent cuts; preview of Chandy-Lamport snapshot algorithm  
Friday, 4/19 Lecture 7: Chandy-Lamport snapshot algorithm; uses of snapshots Programming assignment 2A due; programming assignment 2B out; deadline to drop or add classes
Monday, 4/22 Lecture 8: Chandy-Lamport wrap-up: limitations, assumptions, properties; centralized vs. decentralized algorithms Optional creative project announced
Wednesday, 4/24 Lecture 9: recap of delivery guarantees and protocols; safety and liveness; reliable delivery; fault classification and fault models  
Friday, 4/26 Lecture 10: recap: fault classification and fault models; two generals problem; implementing reliable delivery; idempotence; at-least-once/at-most-once/exactly-once delivery; unicast/broadcast/multicast; reliable broadcast Programming assignment 2B due
Monday, 4/29 Lecture 11: implementing reliable broadcast; introduction to replication; total order vs. determinism; strong consistency (informally)  
Wednesday, 5/1 Lecture 12: consistency models: FIFO, causal, “strong”; primary-backup replication; chain replication; latency and throughput; midterm review  
Friday, 5/3 Midterm exam  
Monday, 5/6 Lecture 13: handling node failure in replication protocols; introduction to consensus; problems equivalent to consensus; the FLP result; introduction to Paxos  
Wednesday, 5/8 Guest lecture: Deniz Altınbüken (Google)  
Friday, 5/10 Lecture 14: Paxos: the interesting cases Programming assignment 3 out
Monday, 5/13 Lecture 15: Paxos wrap-up: nontermination, Multi-Paxos, fault tolerance; other consensus protocols: Viewstamped Replication, Zab, Raft; passive vs. active (state machine) replication  
Wednesday, 5/15 Lecture 16: eventual consistency; strong convergence and strong eventual consistency; intro to application-specific conflict resolution; network partitions; availability; the consistency/availability trade-off  
Friday, 5/17 Guest lecture: Faisal Nawab  
Monday, 5/20 Lecture 17: 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/22 HACK DAY (no lecture)  
Friday, 5/24 Lecture 18: more about quorum consistency; introduction to sharding; consistent hashing Programming assignment 3 due; programming assignment 4 out
Monday, 5/27 No class (Memorial Day)  
Wednesday, 5/29 Lecture 19: 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
Friday, 5/31 Lecture 20: MapReduce: types, approach to fault tolerance, combine functions, more examples Optional creative project due
Monday, 6/3 Guest lecture: Jacob Repp (Blizzard Entertainment)  
Wednesday, 6/5 Lecture 21: the math behind replica conflict resolution: recap of strong convergence; recap of partial orders; upper bounds, least upper bounds, join-semilattices  
Friday, 6/7 Lecture 22: research topic: domain-specific solvers for distributed consistency; final review; AMA Programming assignment 4 due
Thursday, 6/13 Final exam