Distributed Systems
Lecture notes for course CSE138, Spring 2020 given by Prof Lindsey Kuper, Assistant Professor of Computing at UCSC
Due to the Covid-19 lockdown being enforced at the time, these lectures had to be delivered online and are available on YouTube and Twitch
This series of lectures also includes a discussion panel with recent grad students and two guest lecturers. Notes have not been created for these events; however, you can watch the videos here:
- "Grad Student Discussion Panel" Lindsey Kuper talks with Emma Gomish, Pete Wilcox and Lawrence Lawson. May 15th, 2020
- "Blockchain Consensus" by Chris Colohan, May 27th, 2020
- "Building Peer-to-Peer Applications" by Karissa McKelvey, June 3rd, 2020
| Date | Description | Subjects Recapped |
|---|---|---|
| Lecture 1 | There are no notes for this lecture as it was concerned with course administration and logistics | |
| Lecture 2 April 1st, 2020 |
Distributed Systems: What and why? Time and clocks |
|
| Lecture 3 April 3rd, 2020 |
Lamport diagrams Causality and the "happens before" relation Network models State and events Partial orders |
|
| Lecture 4 April 6th, 2020 |
Total orders and Lamport clocks | Partial orders Happens before relation |
| Lecture 5 April 8th, 2020 |
Vector clocks Protocol runs and anomalies Message Delivery vs. Message Receipt FIFO delivery |
Lamport Clocks |
| Lecture 6 April 10th, 2020 |
Causal delivery Totally-ordered delivery Implementing FIFO delivery Preview of implementing causal broadcast |
Delivery vs. Receipt FIFO delivery |
| Lecture 7 April 13th, 2020 |
Implementing causal broadcast Uses of causality in distributed systems Consistent snapshots Preview of the Chandy-Lamport snapshot algorithm |
Causal anomalies and vector clocks |
| Lecture 8 April 15th, 2020 |
Chandy-Lamport Snapshot Algorithm | |
| Lecture 9 April 17th, 2020 |
Chandy-Lamport wrap-up: limitations, assumptions and properties Uses of snapshots Centralized vs. decentralized algorithms Safety and liveness |
Delivery guarantees and protocols |
| Lecture 10 April 20th, 2020 |
Reliable delivery Fault classification and fault models The Two Generals problem |
Safety and liveness |
| Lecture 11 April 22nd, 2020 |
Implementing reliable delivery Idempotence At-least-once/at-most-once/exactly-once delivery Unicast/Broadcast/Multicast Reliable broadcast Implementing reliable broadcast Preview of replication |
|
| Lecture 12 April 24th, 2020 |
Replication Total order vs. determinism Consistency models: FIFO, causal and strong Primary-backup replication Chain replication Latency and throughput |
|
| Lecture 13 April 27th, 2020 |
Pause for breath! Wrapping up replication techniques |
|
| Lecture 14 May 1st, 2020 |
Handling node failure in replication protocols Introduction to consensus Problems equivalent to consensus The FLP result Introduction to Paxos |
Strongly consistent replication protocols |
| Lecture 15 May 4th, 2020 |
Paxos: the interesting parts | |
| Lecture 16 May 6th, 2020 |
Paxos wrap-up: Non-termination, Multi-Paxos, Fault tolerance Other consensus protocols: Viewstamped Replication, Zab, Raft Passive vs. Active (state machine) replication |
|
| Lecture 17 May 8th, 2020 |
Eventual consistency Strong convergence and strong eventual consistency Introduction to application-specific conflict resolution Network partitions Availability The consistency/availability trade-off |
|
| Lecture 18 May 11th, 2020 |
Dynamo: A review of old ideas
|
|
| Lecture 19 May 13th, 2020 |
More about Quorum Consistency Introduction to sharding Consistent hashing |
|
| Lecture 20 May 18th, 2020 |
Online systems vs. Offline systems Raw data vs. Derived data Introduction to Google's MapReduce framework MapReduce example: transform a forward index into an inverted index |
|
| Lecture 21 May 20th, 2020 |
MapReduce
|
MapReduce phases |
| Lecture 22 May 29th, 2020 |
The math behind replica conflict resolution
|
Strong convergence Partial orders |
| Lecture 23 June 1st, 2020 |
Filling in the gaps: Overviews of 2-phase commit and Practical Byzantine Fault Tolerance (PBFT) Quick overview of the history of:
|