The Consensus Problem
Imagine you're at a restaurant with friends, trying to decide where to eat next. Everyone has opinions. Some people aren't responding to texts. One friend keeps changing their mind. How do you reach agreement?
Now imagine this, but with servers. In a distributed system. At scale. With lives or money on the line.
Welcome to the consensus problem.Why Consensus Matters
Leader Election
Which node is the primary database? All nodes must agree.
Distributed Locks
Only one process can hold a lock. Agreement is essential.
Atomic Commits
All nodes commit or all abort. No partial transactions.
State Machine Replication
All replicas process the same commands in the same order.
The Byzantine Generals Problem
The classic thought experiment that defines the challenge:
The Scenario
Several Byzantine generals surround a city. They must agree to attack or retreat. But:
- Messengers might be killed (messages lost)
- Some generals might be traitors (Byzantine faults)
- They must all attack together or all retreat - partial action means defeat
The traitor might tell A "I'll attack" and tell B "I'll retreat." How do the honest generals reach agreement despite the traitor?
Two Types of Failures
Crash Failures
A node stops working completely.
- Predictable: either responds or doesn't
- Easier to handle
- Most consensus algorithms focus here
Byzantine Failures
A node behaves arbitrarily or maliciously.
- Unpredictable: can lie, change messages
- Much harder to handle
- Required for blockchain, etc.
Most distributed systems (databases, coordination services) assume crash failures only. Byzantine fault tolerance is needed for trustless environments like blockchains.
The FLP Impossibility Result
In 1985, Fischer, Lynch, and Paterson proved a sobering theorem:
FLP Impossibility
In an asynchronous system where even one node can crash, it's impossible to guarantee consensus will be reached in bounded time.
Wait, if consensus is impossible, how do real systems work?
Assume synchrony (bounded delays) with timeouts. Works in practice.
Use random delays to break symmetry. Eventually terminates with high probability.
Use heartbeats to detect failures. Can be wrong, but enables progress.
Properties of Consensus
A correct consensus protocol must satisfy:
-
Agreement
All non-faulty nodes decide on the same value
-
Validity
The decided value must have been proposed by some node
-
Termination
All non-faulty nodes eventually decide (liveness)
-
Integrity
A node decides at most once
The Split Brain Problem
Why can't we just vote?
5 nodes, network partition splits them 2-3:
Each partition might elect its own leader. Both think they're in charge. Data corruption follows.
Consensus protocols ensure only one side can make progress - the one with the true majority (quorum).Quorums: The Key Insight
Any two quorums must overlap by at least one node. If quorum = majority (N/2 + 1), then any two majorities share at least one node. This node ensures consistency.
5 nodes, quorum = 3
Quorum A: [1, 2, 3]
Quorum B: [3, 4, 5]
↑
Overlap!Node 3 participated in both decisions. It can ensure consistency.
Real-World Impact
Uses Paxos for consensus across globally distributed data centers. Handles millions of transactions per second with strong consistency.
Uses Raft for cluster state management. Every Kubernetes cluster relies on consensus to agree on pod placements, configurations, and secrets.
Key Takeaways
- Consensus = Agreement - Getting nodes to agree despite failures
- Byzantine vs Crash - Most systems assume crash failures only
- FLP says it's hard - But practical systems use timeouts
- Quorums are key - Overlapping majorities ensure consistency
Next up: Understanding Paxos - The foundational consensus algorithm.