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