/DistributedSystemNotes

Notes on Lindsey Kuper's lectures on Distributed Systems

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:

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
  • Availability
  • Network partitions
  • Eventual consistency
  • Vector clocks
  • Application-specific conflict resolution
Introduction to:
  • Anti-entropy with Merkle trees
  • Gossip
  • Quorum consistency
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
  • Types
  • Approach to fault tolerance
  • Combine functions
  • More examples
MapReduce phases
Lecture 22
May 29th, 2020
The math behind replica conflict resolution
  • Upper bounds
  • Least upper bounds
  • Join-semilattices
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:
  • Lamport and Vector Clocks
  • Replication Strategies
  • Consensus
  • Replication Needs Consensus