How Machines Come to Agree: Distributed Consensus from FLP to Paxos to Raft

The Hook: The Hardest Easy Problem in Computer Science

Picture a mundane question: three friends want to agree on a restaurant. No problem — they talk, they vote, they go eat. Now make it harder, step by step. The three may only exchange written notes. Some letters arrive hours late, some never arrive at all. One friend might fall asleep in the middle of the exchange and only wake up hours later — with no warning, and no outside observer can tell whether he is asleep or whether his letter is simply still in transit. And yet, in the end, all the awake friends must land on the same restaurant, and it must be one that was actually proposed.

This sounds almost trivial, but it is one of the deepest and most consequential problems in distributed computing: the consensus problem. Every time a group of machines must jointly make a binding decision — which server is currently the leader, which transaction counts as committed, what value sits in this database cell — this problem is running in the engine room. It is the foundation on which etcd, and therefore all of Kubernetes, rests, on which CockroachDB, Consul, TiKV, ZooKeeper, and ultimately large parts of today's cloud infrastructure are built.

Here is the remarkable part: for this "simple" problem, there exists a mathematical proof that under realistic assumptions it is fundamentally unsolvable. And yet we solve it millions of times a day. This apparent contradiction is not a scandal; it is the core of one of the most elegant stories in computer science — a story about how you reformulate an impossible problem so precisely that it becomes tractable in practice after all.

This article takes you the whole way: from the exact definition of what consensus actually demands, through the famous FLP impossibility result, on to Paxos — Leslie Lamport's notoriously hard-to-grasp but foundational solution — and finally to Raft, the algorithm whose stated design goal was understandability and which for that reason dominates practice today. At the end stands a way of thinking that reaches well beyond distributed systems.

Part 1: What Consensus Really Demands

Three properties that together make the trouble

Before we talk about solutions, we have to state the problem cleanly. "Agreeing" is a colloquial word; computer science demands precision. When a set of processes each propose a value, a consensus protocol must in the end satisfy exactly three conditions:

Agreement: No two correct processes decide on different values. There must not be two factions at the end that believe different truths were resolved.

Validity: The decided value must actually have been proposed by one of the processes. The protocol may not agree on a freely invented value just to be formally "in agreement."

Termination: Every correct process eventually decides. The protocol may not remain undecided forever.

The first two properties are called safety conditions: they say that "nothing bad ever happens." The third is a liveness condition: it says that "eventually something good happens." This distinction will turn out to be the decisive lever of the entire story.

The failure model: what must we plan for?

Why is this hard? Because the real world of distributed systems has unpleasant properties, gathered together in a failure model. The theoretical classic is the asynchronous system with crash failures. Three ingredients make it toxic.

First, asynchrony: there is no upper bound on how long a message may be in transit, and no bound on how differently fast processes compute. A message may take one millisecond or one hour — both are "allowed."

Second, crash failures: a process may halt permanently at any point, without warning. It does not turn malicious, it does not lie — it simply stops.

Third, and this is the real trap: indistinguishability. In an asynchronous system, an observer cannot in principle tell whether another process has crashed or whether its reply is merely very, very slow. An absent signal has two possible causes, and no outside observation can separate them. The entire drama hangs on this indistinguishability.

Part 2: The Impossibility — the FLP Theorem

A proof that marks the boundaries

In 1985, Michael Fischer, Nancy Lynch, and Michael Paterson published a paper with the sober title Impossibility of Distributed Consensus with One Faulty Process. The result, today known simply as FLP, is one of the most important in computer science and was later honored with the Dijkstra Prize for the most influential work in the field.

The statement is as terse as it is shattering: in a fully asynchronous system there is no deterministic algorithm that is guaranteed to solve the consensus problem if even a single process is allowed to crash. Not "no efficient one," not "none known" — simply none that can exist.

One must stress the subtlety so the result is not over-interpreted: FLP does not say that consensus always fails. It says that every correct algorithm possesses at least one infinite execution in which no decision is ever reached. So there is no algorithm that guarantees safety and termination simultaneously and under all circumstances. Safety (never two contradictory decisions) can always be preserved — but no one can guarantee that a decision is reached at all if the network dawdles in the most adversarial possible way.

The idea of the proof: the suspended state

The proof is elegant and worth an intuitive sketch. Consider the possible system states and sort them into three kinds: states from which only "0" can still be decided; states from which only "1" can still be decided; and bivalent states, from which, depending on what happens next, either outcome is still possible — the result is still suspended.

Fischer, Lynch, and Paterson show two things. First: every correct consensus protocol has an initial bivalent state — at the start the decision is still open. Second, and this is the trick: from any bivalent state you can reach another bivalent state by cleverly delaying exactly one message. The adversary — think of a malicious network scheduler — never has to force the decision; it merely has to keep holding back the one critical message until the system tips into the next suspended state. This creates an infinite chain of bivalence: the system never decides. And because the scheduler never actually loses a message (it only delays it, finitely but arbitrarily long), it violates not a single rule of the asynchronous model.

Why the world works anyway

If consensus is provably impossible — how can Kubernetes run? The answer lies in a fine gap in the FLP model. FLP assumes perfect asynchrony: messages may take arbitrarily long without ever violating a bound. The real world is milder. Most of the time networks respond within milliseconds; long delays are rare and temporary.

Practical algorithms exploit exactly this. They give up the uncompromising guarantee "always terminates" and replace it with: "always terminates whenever the network behaves sufficiently well for a while." Safety they hold unconditionally — so they never make a wrong or contradictory decision, no matter how chaotic the network. Only liveness is tied to a mild assumption about reality. This is formalized, for instance, via timeouts (which produce a suspicion "it has probably crashed") or via partial synchrony (Dwork, Lynch, Stockmeyer 1988: a bound exists, but only takes effect after some unknown point in time). FLP can also be circumvented by randomization. But the practical compromise, almost everywhere, reads: safety always, liveness almost always. Remember this formula — it is the key to both Paxos and Raft.

Part 3: Paxos — the Foundational Solution

The parliament nobody understood

In 1989 — though it was published only in 1998 — Leslie Lamport (the same man whose logical clocks featured in the Spanner article; see Clocks That Know Their Own Uncertainty: Google Spanner, TrueTime, and Mastering Time in the Cloud) wrote the paper The Part-Time Parliament. He dressed the algorithm in an allegory: a fictional parliament on the Greek island of Paxos, whose legislators are present only part-time and must nonetheless pass consistent decrees. The wrapping was so ornate that the field ignored or misunderstood the actual algorithm for years. In 2001, Lamport half-ironically capitulated and wrote Paxos Made Simple — four pages that drop the allegory and state the core in plain language. The famous first sentence runs, roughly: "The Paxos algorithm, when presented in plain English, is very simple." Many readers still found it excruciatingly hard — a circumstance that later motivated Raft in the first place.

Three roles and one promise

Paxos distributes the work across three logical roles, which one and the same machine can play at the same time. Proposers propose values (typically on behalf of a client). Acceptors form the collective memory: they accept or reject proposals, and their majority decides what holds. Learners finally learn which value was chosen and execute it.

The decisive building block is the majority (the quorum). A value counts as chosen precisely when a majority of the acceptors has accepted it. Why a majority? Because any two majorities overlap in at least one acceptor. That one shared acceptor is the silent hero of the whole procedure: it prevents two different majorities from unknowingly choosing two different values. The intersection of two majorities is never empty — and that is exactly what carries the safety guarantee.

The two phases

Basic Paxos chooses a single value in two rounds. Every proposal carries a unique, monotonically increasing proposal number.

In Phase 1 (Prepare), a proposer sends a Prepare(n) message with its number n to a majority of the acceptors. An acceptor that receives n makes two promises, provided n is greater than anything it has seen so far: first, it will henceforth ignore all proposals with a smaller number; second, it tells the proposer whether it has already accepted a value — and if so, which one and with what number.

In Phase 2 (Accept), the proposer evaluates the replies. If any acceptor has already accepted a value, then the proposer may not push through its own preferred value but must adopt the value with the highest already-accepted number. Only if no acceptor has ever accepted a value is it free to choose its own. This value it sends as Accept(n, value) to the majority. If enough acceptors accept, the value is chosen.

The initially counterintuitive rule in Phase 2 — "adopt the foreign value" — is the actual heart of the matter. It ensures that a value chosen once (possibly unnoticed) can no longer be overwritten by any later proposal. Once a value has been accepted by a majority, every later proposer will inevitably, in Phase 1, encounter at least one acceptor that knows this value and will then carry it forward itself. So the decision remains stable, no matter how many proposers appear or crash simultaneously.

Multi-Paxos and the problem of understandability

Basic Paxos agrees on one value. But a real database needs a whole sequence of decisions — entry 1, entry 2, entry 3 — effectively a replicated log (kin to the idea of the immutable event log; see The Logbook of Truth: Understanding Event Sourcing and CQRS). The naive solution, running a full two-phase Paxos for every entry, is expensive. Multi-Paxos optimizes this: a proposer that has established itself once as a stable leader may skip Phase 1 and go straight to Phase 2 for many log entries. That is fast — but the papers left many details open: how exactly does one elect this leader? How does one handle gaps in the log? How does one change the membership set during operation? Every company implemented its own variant, and no two were alike. This very gulf between the elegant core and the underspecified practical scaffolding was the breeding ground for Raft.

Part 4: Raft — Understandability as a Design Goal

An algorithm with an unusual objective function

In 2014, Diego Ongaro and John Ousterhout of Stanford University introduced Raft, in the paper with the programmatic title In Search of an Understandable Consensus Algorithm. Their stated primary goal was unusual for an algorithm: not, in the first instance, speed or a minimal message count, but understandability. It produces a result equivalent to Multi-Paxos and is similarly efficient — but its structure is deliberately built so that a human can hold it in their head. The authors even ran a user study: students demonstrably understood Raft more easily than Paxos.

The central didactic move: Raft decomposes the problem into three largely independent subproblems — leader election, log replication, and safety — and enforces a stronger coherence to reduce the number of states one must consider.

A strong leader and terms

Raft makes a design decision that Paxos shies away from: a strong leader. At any given time exactly one node is the leader; all client requests run through it, and the data flow goes exclusively from the leader to the followers. This makes the system easier to reason about, because there is a single place where truth originates.

Raft divides time into terms — consecutively numbered periods, each beginning with an election. A term is Raft's logical clock: every message carries the term number, and a node that sees a higher term number than its own immediately recognizes it is stale, steps down, and updates itself. A term has at most one leader; some terms end inconclusively (a tie vote), and then the next one simply begins.

Every node is at any time in one of three states: follower (passive, follows the leader), candidate (currently campaigning for leadership), or leader.

Leader election

Followers expect regular heartbeat messages from the leader. If these fail to arrive for a randomly chosen span (the election timeout), the follower suspects the leader is dead, increments its term number, switches to the candidate state, and asks the others for votes (RequestVote). Each node grants at most one vote per term, on a first-come-first-served basis. If a candidate receives votes from a majority, it becomes leader and immediately begins sending heartbeats to cement its authority.

The elegant trick against endless stalemates is the randomized timeouts. Because each node rolls a slightly different waiting time (say 150–300 ms), usually only one starts the election, wins it quickly, and thereby ends the race before others even set off. If a tie does occur, fresh rolls in the next round almost surely produce a prompt decision. This is FLP in action: termination is not guaranteed, but practically certain — exactly the compromise from Part 2.

Log replication

Once a leader is in place, it accepts client commands, appends each as a new entry to its own log, and sends it via AppendEntries to all followers. Every log entry carries the command, the term, and an index. Once a majority of nodes has stored the entry, it counts as committed: now — and only now — the leader applies it to its state machine and reports success to the client. Committed entries are never lost.

To keep the logs consistent, the Log Matching property holds: every AppendEntries message contains the index and term of the immediately preceding entry. If this does not match on the follower, it rejects, and the leader backtracks until both logs find a common point; from there the leader overwrites the divergent follower entries with its own. So all logs inevitably converge on the leader's version.

The safety guarantee

The subtlest part is ensuring that a new leader does not "forget" any already-committed entries. Raft solves this via an election restriction: a candidate gets a vote only if its own log is at least as up-to-date as the voter's (compared via the term and index of the last entry). Because a committed entry by definition sits on a majority, and because every election requires a majority, the two sets overlap: the future leader must already possess every committed entry. So only a node that knows the complete committed history can win. This one condition is the backbone of Raft's safety — and a prime example of how the quorum-overlap argument from Paxos reappears in Raft in an understandable form.

Part 5: The Mathematics of Fault Tolerance

Why it is almost always odd numbers

Both Paxos and Raft need a majority for every decision (\(\lfloor N/2 \rfloor + 1\) of \(N\) nodes). From this follows a simple but often misunderstood formula: to survive \(f\) simultaneous crash failures, you need \(N = 2f + 1\) nodes.

The table explains why production clusters almost always use odd node counts. A 4-node cluster tolerates exactly as many failures as a 3-node cluster (namely one), but costs one more server and demands a reply from three instead of two for every decision — worse in every respect. The jump from 3 to 5, by contrast, genuinely raises fault tolerance from one to two. Odd sizes therefore maximize resilience per server.

Split-brain and why the minority must stay silent

The most important practical benefit of the majority rule shows up during a network partition. If a 5-node cluster splits into a group of 3 and a group of 2, then only the group of three can form a majority and keep working. The group of two can elect no leader and commit no writes — it refuses until the connection returns. This is not a bug but the central protective function: it prevents the dreaded split-brain, in which two sub-clusters would independently make contradictory decisions. Better for the minority to stand still than to destroy consistency. Here the compromise from Part 2 pays off again: safety is preserved unconditionally, availability on the minority side is sacrificed — a direct consequence of the CAP theorem.

Part 6: Consensus in the Wild

Theory is no end in itself; today it runs in practically every serious cloud infrastructure.

etcd and Kubernetes. etcd is a distributed key-value store that implements Raft and holds the entire cluster state of Kubernetes. Every state change — a new pod, a changed deployment — goes through Raft consensus in etcd. If etcd fails without a majority, the Kubernetes control plane "freezes": running containers stay alive, but no new decisions can be made. The etcd Raft library has for years been considered one of the most widely used in the world, serving tens of thousands of clusters daily.

Consul by HashiCorp combines service discovery, health checks, and a KV store. For cluster membership it uses a gossip protocol (Serf), but for the consistent state it uses Raft.

CockroachDB and TiKV push the idea to its limit. A single Raft group does not scale across terabytes, because a single leader would become the bottleneck. So both split the data into many ranges and run a separate Raft group per range — Multi-Raft. This spreads the consensus load across the whole cluster.

Google Spanner, finally, uses Paxos groups for the replication of each data range and combines that with the TrueTime clock from the earlier article. There, consensus provides the ordering within a replication group, and TrueTime provides the globally consistent time between them — two building blocks that together carry external consistency.

What consensus does not solve: Byzantine failures

An important limit: Paxos and Raft assume crash failures — a node stops, but it never lies. It sends no contradictory or maliciously forged messages. If that assumption fails — say because a node was compromised or hardware answers in bizarrely faulty ways — one speaks of Byzantine failures (after Lamport's "Byzantine Generals Problem"). Defending against these requires different, more expensive algorithms (PBFT and successors) and, as can be shown, \(N = 3f + 1\) nodes instead of \(2f + 1\). Blockchains with mutually distrustful participants operate in exactly this Byzantine world; classic cloud infrastructure, by contrast, trusts its own servers and gets by with the cheaper crash model.

A Framework to Take Away: Paxos vs. Raft

Both algorithms rest on the same mathematical foundation — the non-empty intersection of two majorities. The difference is less technical than didactic in nature: at many points Raft makes a concrete, somewhat more restrictive choice where Paxos leaves a degree of freedom open. This self-restriction costs theoretical generality and in return wins something immensely valuable: an algorithm that a team can actually implement correctly.

The Central Takeaway

The deepest lesson of this story is not a particular protocol but an attitude toward dealing with impossibility. FLP proves that you cannot have safety and termination simultaneously and unconditionally. The naive reaction would be resignation. The ingenious reaction was to reformulate the problem: safety is never given up, liveness is tied to a mild assumption about reality. You forgo an absolute promise that theory forbids anyway, and trade it for a conditional one that practice almost always keeps.

For everyday engineering work, there is a transferable way of thinking in this. The next time you face a seemingly impossible requirement — "always available and always consistent and distributed across continents" — do not look for a way to break the laws of nature, but for the one property you must hold unconditionally (usually safety: no data corruption) and the other you may tie to a condition (usually availability: "as long as a majority is reachable"). Consensus algorithms are the canonical example that you win a provably unsolvable problem by ceasing to demand the wrong thing.

And very concretely: the next time you size an etcd, Consul, or CockroachDB cluster, choose an odd node count (3, 5, or 7), distribute the nodes across failure zones so that no single zone holds the majority, and be aware: the moment the majority becomes unreachable, your system should rather refuse writes than risk consistency. This silence of the minority is not a defect — it is the proof that the algorithm is working.

A Question to Reflect On

In your own system landscape: in which component are you currently making an implicit consensus decision without a real consensus mechanism behind it — say, two services that independently decide who is "the active one," or a distributed cache whose nodes might drift apart during a partition? And in that component, in the worst case, would you be willing to sacrifice the availability of the minority to save consistency — or is it exactly the other way around, and you need no strict consensus there at all?

Cross-References in the Vault

• Clocks That Know Their Own Uncertainty: Google Spanner, TrueTime, and Mastering Time in the Cloud – Spanner uses Paxos groups for replication and complements them with TrueTime; also Lamport's logical clocks.
• The Logbook of Truth: Understanding Event Sourcing and CQRS – the replicated log as the "single source of truth" is the shared mental figure of consensus and event sourcing.

Sources

• Fischer, Lynch, Paterson (1985): Impossibility of Distributed Consensus with One Faulty Process. FLP paper (PDF) · Explanation of the proof (INRIA ANTIQUE)
• Lamport (1998/2001): The Part-Time Parliament and Paxos Made Simple. Paxos Made Simple (PDF)
• Ongaro, Ousterhout (2014): In Search of an Understandable Consensus Algorithm (Raft). Raft paper (PDF) · USENIX ATC '14
• etcd Raft library (GitHub) – reference implementation behind Kubernetes and many other systems.
• Consul Consensus (HashiCorp) – Raft in a production system.

← All articles