Consensus and Coordination: Raft, Paxos, and Why Agreement Is Hard

June 3, 2026 11 min read Software Architecture

distributed-systemsconsensusraftpaxosarchitecturereliability

Contents

Underneath an enormous amount of the infrastructure you run every day sits a single, deceptively hard problem: getting a group of machines to agree on something. Which node is the leader. What the next entry in the log is. Whether a transaction committed. This is the consensus problem, and it is the beating heart of etcd (which holds all of Kubernetes’ state), Consul, ZooKeeper, Kafka’s metadata layer, and every distributed database with a notion of “the truth.” If you understand consensus, a huge swath of distributed systems stops being mysterious. This post builds that understanding from the ground up — not the proofs, but the intuitions an engineer needs to reason about these systems when they misbehave.

This is the first post in a distributed-systems fundamentals series. It pairs with the consistency and replication post (what guarantees you get) and the time and ordering post (how to coordinate without a shared clock).

Why agreement is hard

Agreement among humans in a room is easy: everyone hears the same proposal, raises a hand, done. Distributed agreement is hard because the environment is adversarial in mundane ways:

Messages can be lost, delayed, duplicated, or reordered. The network gives you no guarantees.
Nodes can crash at any moment — including halfway through telling others what they decided.
You cannot tell a crashed node from a slow one. A node that has not replied might be dead, or might be about to reply after a GC pause. This ambiguity is the source of most of the difficulty.
There is no shared clock to order events globally (the subject of the third post in this series).

Put together, these mean you cannot simply “ask everyone and take a vote,” because some of “everyone” may be unreachable, some answers may be in flight, and you can never be sure a silent node is gone. Consensus algorithms are the carefully-designed protocols that reach agreement despite all of this.

A correct consensus protocol must guarantee, even under failures:

Agreement (safety): no two nodes decide different values. This must never be violated — a split decision is corruption.
Validity: the value decided was actually proposed by someone (no inventing values).
Termination (liveness): the protocol eventually decides, assuming enough nodes are up and can communicate.

Holding safety and liveness together under arbitrary failures is the whole game — and, as we will see, there is a fundamental limit to how well you can do it.

The FLP impossibility result, in plain terms

In 1985, Fischer, Lynch, and Paterson proved a result that every distributed-systems engineer should know the shape of, even without the math:

In a fully asynchronous system where even one node may crash, there is no deterministic consensus algorithm that is guaranteed to always terminate.

“Asynchronous” here means there is no bound on message delay — a message might take any amount of time. The intuition: because you cannot distinguish a crashed node from an arbitrarily slow one, any protocol can be forced into an endless wait by unlucky-but-legal timing, with no point at which it is safe to decide.

This sounds like it should doom the whole field. It does not, and understanding why it doesn’t is the key insight:

FLP forbids a protocol that is always both safe and live in a fully asynchronous model. Real protocols keep safety unconditionally (they never decide wrong) and sacrifice guaranteed liveness in the rare pathological case — they may stall during extreme network chaos, but they never produce a wrong answer.
Real systems are not fully asynchronous. Networks are usually well-behaved, so protocols add timeouts and randomization to make progress in practice. The timeout is an assumption that “a node silent this long is probably dead,” which lets the protocol move forward. It is occasionally wrong (a slow node gets falsely declared dead), but the safety machinery handles that.

So the practical reading of FLP is: you can always stay correct, but you cannot guarantee you will always make progress — you trade a little liveness for safety, using timeouts to make stalls rare. Every protocol below lives inside this trade.

The two pillars: majorities and leaders

Almost every practical consensus system rests on two ideas.

Quorums and majorities

You cannot require all nodes to agree, because then a single failure halts everything. Instead, decisions require a quorum — typically a strict majority of nodes. With 5 nodes, any 3 form a majority. The magic property is that any two majorities overlap in at least one node. That overlap is what prevents two conflicting decisions: a value can only be chosen if a majority accepted it, and since two majorities share a node, they cannot have chosen different values.

  5-node cluster. Majority = 3.

  Group A: {n1, n2, n3}      Group B: {n3, n4, n5}
                 └──── overlap at n3 ────┘
  n3 can't have accepted two conflicting values
  → no split decision possible

This is why consensus clusters are sized at odd numbers (3, 5, 7): an odd count maximizes failure tolerance per node. A 5-node cluster tolerates 2 failures (3 remain = majority); a 4-node cluster also only tolerates 1 failure to keep a majority of 3, so the extra node buys nothing. The general rule: a cluster of 2f+1 nodes tolerates f failures.

A leader to cut through the noise

Reaching agreement among equals on every single value is slow and intricate. The dominant practical simplification is to elect one leader that sequences all decisions. Followers replicate what the leader says. This turns “everyone negotiate every value” into “elect a leader occasionally, then let it dictate the order,” which is far simpler and faster — as long as you can correctly handle the leader crashing.

Paxos: correct, and famously hard

Paxos, introduced by Leslie Lamport in 1998, was the first proven-correct consensus algorithm, and for two decades it was the answer. It works through roles (proposers, acceptors, learners) and a two-phase protocol (prepare/promise, then accept/accepted) built around majority quorums and monotonically increasing proposal numbers. It is provably safe.

Its problem is not correctness but comprehensibility and practicality. Basic Paxos decides a single value; real systems need a continuous stream of decisions, which requires Multi-Paxos, whose details Lamport’s papers left underspecified. The result was a generation of engineers who found Paxos genuinely difficult to understand and even harder to implement correctly — the gap between the elegant single-value proof and a working replicated log was wide and full of subtle traps. Paxos still runs in serious systems (Google’s Chubby, Azure Storage’s replication layer), but it earned a reputation as something only experts should implement from scratch.

Raft: consensus designed to be understood

In 2014, Ongaro and Ousterhout published Raft with an explicit, unusual goal: not to be cleverer than Paxos, but to be understandable. They decomposed consensus into three sub-problems a person can reason about separately, and Raft promptly took over the industry.

The three pieces:

1. Leader election. Time is divided into terms (a monotonic counter). Each node is a follower, candidate, or leader. If a follower hears nothing from a leader within a randomized election timeout, it becomes a candidate, increments the term, and requests votes. A node grants one vote per term; a candidate that wins a majority becomes leader. The randomized timeout is the clever bit — it makes simultaneous candidacies (split votes) rare, so elections usually resolve in one round.

2. Log replication. The leader takes every client request as a log entry and replicates it to followers. Once a majority has stored an entry, the leader marks it committed and applies it to the state machine. Followers apply committed entries in the same order, so every node’s state machine walks through identical states — this is state machine replication, the foundation of how these systems stay consistent.

3. Safety. Raft adds restrictions ensuring a node can only win an election if its log is at least as up-to-date as the majority’s, so a newly elected leader never lacks a committed entry. Committed history is never lost or overwritten.

   Raft normal operation
   ─────────────────────
   Client ──► Leader ──┬──► Follower 1   (append entry)
                       ├──► Follower 2
                       └──► Follower 3
                            │
              majority stored the entry?
                            │ yes
                            ▼
              Leader marks COMMITTED, applies to state machine,
              tells followers to apply → all replicas converge

Why Raft won: it has a strong, single leader (simpler than Paxos’s more symmetric design), an explicit and well-specified protocol for the full replicated log (not just one value), and a presentation built for human understanding. The practical payoff is that correct, well-tested Raft implementations are now widely available, and the protocol is the default choice for new systems.

Where this runs (so you recognize it)

Consensus is not academic — it is load-bearing in tools you use daily:

System	Protocol	What it coordinates
etcd	Raft	All of Kubernetes’ cluster state
Consul	Raft	Service discovery, config, service mesh
ZooKeeper	ZAB (a Paxos-family protocol)	Coordination for Hadoop, HBase, and historically Kafka
Kafka (KRaft)	Raft	Cluster metadata — replacing the old ZooKeeper dependency
CockroachDB, TiKV, ScyllaDB	Raft (per data range)	Replicating each shard of the database consistently
Docker Swarm	Raft (SwarmKit)	Cluster state and orchestration
Google Chubby, Azure Storage	Paxos	Locking and consistent replication at hyperscale

A useful pattern to notice: Kafka’s move to KRaft (removing its ZooKeeper dependency by building consensus directly in) reflects the industry trend — fewer external coordination services, more purpose-built Raft embedded right where it is needed.

Reasoning about failure: split-brain, fencing, and a lost leader

The real value of understanding consensus is diagnosing what happens when things break.

Split-brain and why the majority rule saves you

Split-brain is the nightmare scenario: a network partition divides the cluster, and two sides each believe they are in charge, accept conflicting writes, and corrupt the data when they reunite. The majority-quorum rule is precisely the defense: in a 5-node cluster split 3-2, only the side with 3 can form a majority and elect a leader. The minority side cannot make progress — it cannot elect a leader or commit writes, so it correctly refuses to act rather than diverge. This is the single most important operational consequence of quorums: a minority partition goes read-only or unavailable, on purpose, to preserve correctness. “Why did my cluster stop accepting writes during a network blip?” is usually this working as designed.

Fencing: stopping a zombie leader

A subtle failure: a leader is declared dead (it was just slow or partitioned), a new leader is elected, and then the old leader comes back still thinking it is in charge. Now you have two leaders momentarily. Fencing prevents the zombie from doing damage. Raft’s terms are a fencing mechanism: every message carries the term number, and any node seeing a higher term immediately recognizes its own leadership is stale and steps down. The old leader’s writes, stamped with an old term, are rejected by followers who have moved on. (The general pattern — a monotonically increasing “fencing token” that downstream systems use to reject stale actors — is worth knowing beyond Raft; it is how you safely guard any resource a failed-over leader might still touch.)

A cluster that lost its leader

When the leader dies, here is the sequence to expect:

Followers stop hearing heartbeats. For one election-timeout window, the cluster is unavailable for writes — there is no leader to accept them. This brief unavailability is normal and expected.
A follower times out, becomes a candidate in a new term, and requests votes.
If it gathers a majority (so a majority must be alive and connected — back to the quorum requirement), it becomes leader and writes resume. Typical recovery is sub-second to a few seconds.
If no majority can be assembled (too many nodes down, or a bad partition), no leader can be elected and the cluster stays unavailable for writes until enough nodes return. The system chooses unavailability over the risk of split-brain — a deliberate, correct trade you will meet again in the CAP discussion.

This is why these systems are sized and placed carefully: a 3-node cluster tolerates 1 failure, a 5-node tolerates 2, and spreading nodes across failure domains (racks, availability zones) is about preserving a majority when one domain dies.

The mental model to keep

Strip away the details and consensus reduces to a few durable ideas:

Agreement under unreliable networks and crashes is genuinely hard, and FLP says you cannot have guaranteed liveness and safety in a fully asynchronous world — so real systems keep safety absolute and use timeouts to make stalls rare.
Majority quorums make decisions, and the overlap between any two majorities is what prevents conflicting decisions. Odd-sized clusters of 2f+1 tolerate f failures.
A leader sequences decisions for speed and simplicity; log replication to a majority makes entries durable; state machine replication keeps every node’s state identical.
Paxos proved it was possible; Raft made it understandable and is now the default.
Operationally, the majority rule means a minority partition stops on purpose (no split-brain), fencing/terms neutralize zombie leaders, and a leaderless cluster is briefly unavailable by design while it elects a new one.

With that, the behavior of etcd, Consul, Kafka, and your distributed database under failure becomes predictable rather than alarming. Next in the series: once the cluster agrees on a log, what consistency does the data actually offer — CAP, PACELC, and the replication trade-offs you cannot escape.

Sources: