The Consensus Problem
Imagine you have 5 servers working together. They need to agree on something: Who should be the leader? What data to write? Whether to commit a transaction?
If all servers are healthy and the network is perfect, this is easy. But what if:
- A server crashes mid-conversation
- The network drops messages
- Messages arrive out of order
- A server is slow and doesn't respond in time
How do independent machines agree on a single value when they can't reliably communicate and some might fail?
This is the consensus problem, one of the fundamental challenges in distributed systems.
Why Consensus Is Hard
The FLP Impossibility Result
In 1985, Fischer, Lynch, and Paterson proved something shocking: It's impossible to guarantee consensus in an asynchronous system if even one process can fail.
- You can't tell if a process is dead or just slow
- There's no way to wait "long enough" for a response
- Perfect consensus with failure tolerance is mathematically impossible
So How Do We Build Real Systems?
We relax the requirements:
- Add timeouts: Guess when a node is dead (might be wrong sometimes)
- Tolerate temporary disagreement: Eventually consistent instead of always consistent
- Use quorums: Majority agreement is good enough
- Assume bounded delays: Messages arrive within some time limit (usually true in practice)
Leader Election: Practical Consensus
One of the most common consensus problems is leader election. Many distributed systems need a single coordinator:
- GFS Master: One node manages metadata
- Database Primary: One node handles writes
- Cluster Coordinator: One node assigns tasks
When the leader dies, the remaining nodes must elect a new one. This requires consensus!
- Safety: Only one leader at a time (no split-brain)
- Liveness: Eventually, a leader is elected (system makes progress)
- Fault Tolerance: Works even if some nodes fail
The Bully Algorithm
One of the simplest leader election algorithms is the Bully Algorithm (Garcia-Molina, 1982). It's called "Bully" because the highest-ID process always becomes leader, bullying the others.
How It Works
Each process has a unique ID (e.g., 1, 2, 3, 4, 5). The process with the highest ID becomes the leader.
The Algorithm Steps
// When a process detects the leader is dead:
1. Start Election
- Send ELECTION message to all processes with higher IDs
- Wait for responses (with timeout)
2. If no one responds (I have highest ID):
- Declare myself the leader
- Send COORDINATOR message to all lower-ID processes
3. If someone responds (higher ID exists):
- Step back and wait
- Higher process will run election and declare itself leader
// When receiving ELECTION message from lower-ID process:
4. Respond with OK
5. Start my own election (if not already running one)
Detailed Example
Let's say we have processes [1, 2, 3, 4, 5]. Process 5 is the leader.
Step 1: Process 2 sends ELECTION to [3, 4, 5]
→ Process 3 and 4 respond "OK"
→ Process 5 doesn't respond (it's dead)
Step 2: Process 3 and 4 each start their own election
→ Process 3 sends ELECTION to [4, 5]
→ Process 4 sends ELECTION to [5]
Step 3: Process 4 gets no response (has highest ID)
→ Process 4 declares itself coordinator
→ Sends COORDINATOR to [1, 2, 3]
Result: Process 4 is the new leader ✅
Real Implementation
I implemented the Bully Algorithm in Go with a complete simulation of process crashes and network failures.
Democratic Quorum - Bully Algorithm Implementation
A full implementation showing leader election with:
- Multiple processes communicating over network
- Simulated process crashes
- Election timeout handling
- Coordinator announcements
Bully Algorithm: Pros & Cons
✅ Advantages
- Simple: Easy to understand and implement
- Fast convergence: Quick elections in stable networks
- Deterministic: Highest ID always wins (predictable)
❌ Limitations
- Network traffic: O(n²) messages in worst case
- Assumes synchrony: Needs reliable timeouts
- Highest ID bias: Always favors same node (load imbalance)
Other Consensus Algorithms
Bully is great for learning, but production systems use more sophisticated algorithms:
Raft
Designed for understandability. Uses terms and leader elections with randomized timeouts. Used in etcd, Consul.
→ We'll cover this next!
Paxos
The original consensus protocol. Proven correct but notoriously hard to understand. Used in Google Chubby.
ZAB (ZooKeeper)
Similar to Paxos but optimized for primary-backup replication. Used by Apache ZooKeeper.
Viewstamped Replication
Actually predates Paxos! Uses view numbers and replication for consensus.
Key Takeaways
- Consensus is hard → FLP impossibility proves it's impossible with perfect guarantees
- Leader election → One of the most practical consensus problems
- Bully Algorithm → Simple but effective for teaching and small systems
- Timeouts matter → Distinguishing between slow and dead is critical
- Production needs better → Raft, Paxos for real distributed systems
Coming Next: Raft Consensus
In the next post, we'll dive deep into Raft, the consensus algorithm designed to be understandable. We'll cover:
- Leader election with randomized timeouts
- Log replication across replicas
- Safety guarantees and edge cases
- Why Raft is easier to understand than Paxos