Consensus Algorithms
How Raft and Paxos let distributed nodes agree on a single value — like who's the leader — despite failures.
Overview
Consensus algorithms — RaftA consensus algorithm, designed to be more understandable than Paxos, that elects a leader by majority vote and replicates a log across nodes — used by etcd, Consul, and CockroachDB.Learn more and PaxosThe original majority-vote consensus algorithm for getting distributed nodes to agree on a single value — widely considered harder to understand and implement correctly than Raft.Learn more being the two best-known — let a group of distributed nodes agree on a single value, like who the current leader is, even when some nodes fail or messages are delayed, forming the foundation underneath most distributed databases' replication and coordination.
Why It Exists
Leader-follower replication, covered earlier in this path, assumes a leader exists and is known — but in a real distributed system, nodes need a reliable way to actually elect that leader and agree on it, without ever ending up with two nodes simultaneously believing they're the leader (a Split BrainThe failure mode consensus algorithms exist to prevent — two nodes in a distributed system each believing they're the leader at the same time, both accepting writes independently.Learn more). Consensus algorithms exist to solve exactly this class of problem with a mathematically proven guarantee, not just a best-effort heuristic.
Real World Example
In a Raft-based system (etcd, Consul, and CockroachDB all use Raft internally), if the current leader stops responding, the remaining nodes hold a leader election: each candidate requests votes, and a candidate only becomes the new leader once it receives votes from a majority of all nodes — ensuring at most one leader is ever elected for a given term, even if the network is temporarily partitioned in confusing ways.
Example Data
A Raft leader election — a 5-node cluster needs a majority (3) to elect a new leader
| Node | Vote |
|---|---|
| Node A (candidate) | votes for itself |
| Node B | votes for A |
| Node C | votes for A |
| Node D, Node E | unreachable — don't vote |
How Consensus Actually Works
The Problem: Split Brain
Without a rigorous agreement protocol, a network partition or delayed message could lead two different nodes to each believe they're the leader at the same time — both accepting writes independently, corrupting the data.
Raft — Leader Election by Majority Vote
When no leader is known (or the current one is unresponsive), nodes hold an election. A candidate becomes leader only after receiving votes from a strict majority of all nodes — guaranteeing at most one leader can win for any given term.
Raft — Replicating the Log
Once elected, the leader appends entries to a replicated log and only considers an entry committed once a majority of nodes have stored it — the same majority-based safety property used for elections, applied to data itself.
Paxos — the Older, More General Alternative
Paxos solves the same fundamental problem and predates Raft, but is widely considered significantly harder to understand and implement correctly. Raft was explicitly designed to be more understandable while providing equivalent guarantees.
Diagram
A leader failure triggers an election; only a majority-backed candidate can win
Leader stops responding
Remaining nodes start an election
Each candidate requests votes
Majority reached
new leader confirmed
Log entries replicated from the new leader
Common Mistakes
Assuming any majority-based voting scheme is 'as good as' Raft or Paxos
Why: Consensus algorithms have subtle, rigorously proven correctness properties around exactly when a value is safe to consider final — a hand-rolled, seemingly-similar voting scheme without that rigor can have rare, catastrophic edge cases in precisely the failure scenarios it needs to handle.
Fix: Use a battle-tested consensus implementation (a Raft library, or a system already built on one) rather than designing a custom leader-election scheme from scratch.
Not accounting for consensus's latency cost
Why: Reaching agreement across a majority of nodes takes real network round trips, which adds latency to whatever operation depends on it — like committing a Raft log entry. This is a real, measurable cost, not free coordination.
Fix: Understand that adding more nodes to a consensus group increases fault tolerance but generally doesn't improve, and can hurt, per-operation latency.
Confusing 'majority of nodes' with 'majority of a partition' during a network split
Why: During a partition, only the side holding an actual majority of the total cluster can safely elect a leader and make progress — the minority side correctly refuses to, specifically to prevent split-brain.
Fix: Recognize this as a deliberate CP choice (tying directly back to CAP theorem) — the minority partition being unavailable is the price of preventing split-brain, not a bug.
Interview Questions
What problem do consensus algorithms like Raft solve?
They let a group of distributed nodes reliably agree on a single value — most commonly, who the current leader is — even when some nodes fail or messages are delayed, without risking two nodes both believing they're in charge at once.
Why does a Raft leader election require a majority vote instead of just the first response?
Requiring a strict majority guarantees that at most one candidate can win an election for a given term, since two disjoint majorities can't both exist among the same set of nodes. Accepting just the first response wouldn't prevent two different candidates from each winning votes from different, non-overlapping subsets of nodes at the same time.
During a network partition, one side of a Raft cluster has a majority of nodes and the other doesn't. What happens on each side, and why is that correct?
The majority side can elect a new leader (if needed) and continue processing writes normally, since it can reach the quorum required for both elections and log commits. The minority side cannot elect a leader or commit new writes, and effectively becomes unavailable for writes until the partition heals. This is the correct, deliberate behavior — allowing the minority side to keep accepting writes independently would risk split-brain, so unavailability there is the price paid for consistency, matching the CP side of the CAP theorem trade-off.
Production Best Practices
Do
✓Use a proven consensus library/implementation rather than a custom voting scheme.
✓Account for consensus's real latency cost when sizing a cluster.
✓Understand a minority partition's unavailability as a deliberate, correct CP behavior.
Don't
✗Don't build a custom 'good enough' leader-election scheme instead of using Raft/Paxos.
✗Don't assume adding more nodes to a consensus group always improves performance.
✗Don't treat a minority partition's inability to elect a leader as a bug to work around.
Comparison
| Understandability | Adoption | Core Idea | |
|---|---|---|---|
| Raft | Designed to be understandable | etcd, Consul, CockroachDB | Majority-vote leader election + replicated log |
| Paxos | Notoriously difficult | Older systems, Google Chubby | Majority-based proposal/acceptance rounds |