Distributed Systems: Replication, Consensus and Consistency
Reason precisely about systems that span many machines: clocks, replication, consistency models, Raft consensus and distributed transactions, with simulations you build and break.
Advanced · Computer Science · about 19 hours · 5 modules · certificate on completion
Taught by Wei-Chéng Liú, Élèna Petrovà, AI Learning Companions.
About this course
Most systems now run on many machines, and their hardest bugs come from that: messages that arrive late or twice, clocks that disagree, replicas that diverge, and nodes that each believe they're in charge. This advanced course gives you the precise ideas engineers use to reason about such systems. You'll start from fault and timing models and see why physical clocks can't order events, then use Lamport and vector clocks instead. You'll compare leader-follower, multi-leader and leaderless replication, define consistency models from linearisable to eventual and see what CAP and PACELC really say, study Raft in detail and Paxos in outline, and finish with two-phase commit, sagas and the truth about exactly-once processing.
Every lab is a deterministic Python simulation, so it prints the same result on any laptop: you'll replay a message trace with vector clocks, measure stale reads under different quorums, write a linearisability checker and use it to catch a real quorum anomaly, implement Raft's voting rules and watch elections survive crashes and partitions, and recover a crashed two-phase-commit coordinator. The capstone extends your Raft simulation into a replicated key-value store, checked against Raft's safety properties after every event. The course builds on System Design Fundamentals: Scale, Caching and Load Balancing, and Database Internals: Indexes, Transactions and Query Plans covers what happens inside each node.
What you'll learn
- Explain partial failure, fault and timing models, and why physical clocks can't order events
- Order events with Lamport and vector clocks, and detect concurrent writes with version vectors
- Compare leader-follower, multi-leader and leaderless replication, and choose quorums for a workload
- Define linearisable, sequential, causal and eventual consistency precisely, and test histories against them
- Trace Raft's leader election and log replication, and explain the rules that keep it safe
- Choose between two-phase commit, sagas and idempotent processing for work that spans services
Skills you'll gain
Distributed systems, Logical and vector clocks, Replication, Quorum systems, Consistency models, Linearisability checking, Raft consensus, Distributed transactions, Idempotent processing, Fault-injection simulation
Tools
Python, pytest
Before you start
System Design Fundamentals: Scale, Caching and Load Balancing, or experience with replicas, shards and queues; confident Python, including classes and dataclasses; and comfort with pseudocode and short proofs. Install Python 3.10 or newer and pytest (python -m pip install pytest). Every lab is a deterministic simulation that runs on a laptop: no cluster is needed.
Modules
Failure, time and clocks
Start from what makes distributed systems hard: partial failure, unreliable networks and clocks that disagree. Define the fault and timing models every protocol assumes, then order events without trusting clocks, using Lamport and vector clocks.
- Partial failure and system models (13 min)
- Physical clocks and their limits (12 min)
- Logical clocks: Lamport and vector clocks (14 min)
- Hands-on lab: Order events with Lamport and vector clocks
Replication
Keep copies of data on several nodes: leader-follower replication and its failover hazards, multi-leader replication and conflict resolution, and leaderless replication with quorums, read repair and anti-entropy.
- Leader-follower replication and failover (13 min)
- Multi-leader replication and conflicts (12 min)
- Leaderless replication and quorums (14 min)
- Hands-on lab: Simulate quorum reads and writes
Consistency models and CAP
Say precisely what a replicated system promises: linearisability, sequential and causal consistency, session guarantees and eventual consistency. Then use CAP and PACELC to reason about what each guarantee costs during partitions and in normal operation.
- Linearisability (14 min)
- Sequential, causal and eventual consistency (13 min)
- CAP and PACELC (12 min)
- Hands-on lab: Check histories for linearisability
Consensus: Raft and Paxos
Get a group of nodes to agree despite crashes and an unreliable network: what consensus guarantees and why majorities matter, Raft's leader election, log replication and safety rules in detail, and Paxos in outline.
- The consensus problem (12 min)
- Raft: leader election (14 min)
- Raft: log replication and safety (15 min)
- Paxos in brief (12 min)
- Hands-on lab: Simulate a Raft leader election
Distributed transactions and exactly-once
Make changes that span several nodes or services: two-phase commit and why it blocks, sagas and their compensating actions, and the truth about exactly-once: at-least-once delivery plus idempotent, deduplicated processing.
- Two-phase commit (13 min)
- Sagas and the outbox pattern (12 min)
- Exactly-once: what is and isn't possible (13 min)
- Hands-on lab: Two-phase commit and a saga, with failures
Project: Build a replicated key-value store on Raft
Extend your Module 4 simulator into a replicated key-value store that clients can rely on. Add log replication to raft.py: entries become (term, command) pairs; the leader appends client commands, sends AppendEntries with prevLogIndex, prevLogTerm, the entries and its commit index, and backs off nextIndex after a rejection; followers apply the consistency check and remove conflicting entries; the leader advances its commit index only for current-term entries stored on a majority, and appends a no-op when it takes office; every node applies committed entries in order to a dictionary. Clients send set and get commands to the leader (followers redirect them), each with a client ID and sequence number so that a retried command is applied once, and reads are made linearisable by going through the log or by confirming leadership with a heartbeat round first. Then attack it: run at least five fault scenarios with fixed seeds (a leader crash; a follower crash and restart that keeps its persisted term, vote and log; a partition and heal; 10% message loss; and the Figure 8 case from the Raft paper), call invariants.check_all after every event, and check the history of client operations from a small run with your Module 3 linearisability checker. Finally, write a report on the design, the scenarios, every invariant failure you hit and how you fixed it.
Part of
The products this course names are trademarks of their owners, who haven't made or endorsed it.