Probabilistic and distributed systems · 50 / 53
Paxos, Raft and majority agreement
Understand → trace → implement → justify
2 min reading · allow extra time for practiceConsensus maintains agreement on values or logs despite failures and delays. Safety prevents conflicting committed values; liveness allows progress under suitable conditions. A minority partition may stop writes to preserve safety. Five replicas can tolerate two unavailable replicas under the appropriate crash-fault model.
Paxos uses proposal numbers, promises and accepted values; quorum intersection helps preserve chosen values. Multi-Paxos builds a log. Raft separates leader election, replication and safety rules. Sending a write to a majority of RAM copies is not a complete Raft implementation: terms, log matching, election restrictions, durable storage and commit rules matter.
Crash faults, Byzantine behaviour and client exactly-once semantics differ. Ordinary Raft/Paxos do not promise arbitrary malicious-node tolerance. FLP concerns deterministic termination in a specific fully asynchronous model, not the impossibility of practical consensus. Timeouts, failure detectors and partial synchrony alter progress assumptions. Consensus is not synonymous with blockchain.
A worked trace
With five nodes, quorum size is three. Two such sets intersect; intersection is necessary but not a complete safety proof.
Cost and assumptions
Measure messages, latency, log size and durable I/O; a single Big-O bound does not describe the entire protocol.
Executable example
Run with Python 3. Assertions check a small example; they do not constitute a general correctness proof. Some advanced examples are explicitly small models or reference oracles, not full production implementations.
from itertools import combinations
quorums=list(map(set,combinations(range(5),3)))
assert all(a&b for a in quorums for b in quorums)TEST YOUR UNDERSTANDING
Your turn
Why should a two-node partition not continue committing writes in a five-node cluster?
Reveal the reasoning
It lacks a majority; conflicting decisions must be prevented. Actual commit rules still depend on the protocol.
Take it further
- Write down the input contract and the invariant before changing the example.
- Add empty, boundary, duplicate and adversarial cases where they are relevant. Compare with a simple oracle.
- Derive the cost under the stated model; measure several input sizes and explain discrepancies.
Primary reading & lecture notes
Original explanations in this course; these references provide proofs and further reading. Source links may cover the broader module.
Ongaro & Ousterhout · Raft ↗Leslie Lamport · Paxos Made Simple ↗