Distributed Consensus: From 2PC to Blockchain
A unified tour of how distributed systems agree on a single value — from classic 2PC through Paxos, Raft, PBFT, and Nakamoto-style blockchain consensus.
Consensus is the foundational problem of distributed computing: how do N processes agree on a single value even when some of them fail? The answer determines the consistency guarantees, availability, and fault model of every distributed system in this course.
FLP Impossibility (Fischer, Lynch, Paterson 1985)
In a purely asynchronous distributed system — where there are no timing bounds on message delivery or process speed — it is impossible to deterministically solve consensus if even one process may crash.
The proof shows that any protocol can always be driven into a "bivalent" configuration (where both 0 and 1 outcomes remain reachable) by an adversarial scheduler, preventing termination.
In practice we break one assumption: we use timeouts (Paxos, Raft) — which violate pure asynchrony by introducing weak timing assumptions — or randomization (Ben-Or) to circumvent the impossibility. Blockchains use probabilistic finality rather than deterministic termination.
Protocol Comparison
Six major consensus protocols spanning crash fault tolerance (CFT), Byzantine fault tolerance (BFT), and Nakamoto/blockchain consensus.
| Protocol | Type | Fault Model | Msg Complexity | Leader? | Used In |
|---|---|---|---|---|---|
| 2PC | Atomic commit | Crash (coordinator) | O(N) | Yes | Databases (MySQL, Postgres distributed txns) |
| Paxos | SMR | Crash (f < N/2) | O(N²) | Yes | Chubby, ZooKeeper |
| Raft | SMR | Crash (f < N/2) | O(N) | Yes | etcd, CockroachDB, TiKV |
| PBFT | BFT | Byzantine (f < N/3) | O(N²) | Yes | Hyperledger Fabric |
| PoW | Nakamoto consensus | Byzantine (f < 50% hash) | O(N) | No (probabilistic) | Bitcoin, Litecoin |
| PoS | Nakamoto-style | Byzantine (f < 33% stake) | O(N) | No (stochastic) | Ethereum 2.0, Cardano |
Interactive: Minimum Replicas by Fault Tolerance
CAP Theorem
Every consensus protocol makes a trade-off between consistency and availability under network partition. Crash-fault-tolerant protocols (Paxos, Raft) are CP. Nakamoto consensus (Bitcoin) is more nuanced: it provides eventual consistency (AP-like) but requires honest majority of hash power.
Click a zone (CP, AP, or CA) to see which systems live there and why.
Deep Dives
Consensus Exam Questions
Key questions on the fundamentals — FLP impossibility, 2PC vs Paxos, quorums.