Consensus Algorithm

Definition

A consensus algorithm is a procedure by which several machines, connected only by an unreliable network, agree on a single value in a way that no later failure can contradict. The value is usually mundane — the next entry in a replicated log, which machine currently holds the lease, whether a transaction committed — but the guarantee is unusually strong: the machines may never be caught having decided two different things, whatever crashes, delays or lost packets occur.

The reason this needs an algorithm at all, rather than a vote, is that the participants cannot tell a dead peer from a slow one. Both look identical from the outside: silence. So a protocol that waits for everyone deadlocks the moment one machine dies, and a protocol that proceeds without waiting risks two machines each believing they are in charge.

The idea that resolves this fits in one sentence. Any two majorities of the same group of machines must share at least one member. Take five machines; two subsets of three contain six memberships between them, and there are only five machines to hold them, so at least one machine is in both subsets. Require every decision to be acknowledged by a majority, and that overlapping machine is a witness who remembers the earlier decision and refuses to endorse a conflicting one. Two contradictory decisions become impossible, not merely unlikely. Everything else — leaders, terms, logs, elections — is bookkeeping arranged around that single fact.

Here is what it costs you if you skip it. A common piece of homegrown failover logic reads: the primary stopped answering our health check, so promote the standby. If the primary was alive and merely unreachable, there are now two primaries accepting writes into diverging states, and no procedure exists to merge them afterwards — someone will choose which customers' data to discard. This is split brain, and it is the failure that consensus exists to prevent. A majority rule prevents it because the isolated primary cannot reach a majority, so it cannot commit anything while it is cut off.

How It Works

Majority, and why an even-sized cluster is wasted money

A decision is committed when more than half the machines have durably acknowledged it. That fixes the fault tolerance immediately: to survive f crashed machines you need 2f+1 participants, so that a majority still exists among the survivors.

Read the even rows. Four machines tolerate exactly one failure, which is what three machines already do — the fourth costs money, adds a message to every decision, and buys nothing. Six is no better than five. This is why every production consensus cluster you will meet has three, five or seven members, and why the answer to "should we add a node for extra safety?" is usually no.

A leader turns agreement into replication

Running a full agreement protocol per value is expensive, so real systems elect a leader once and then reuse it. Raft is the clearest expression of this and the one most implementations follow. Time is divided into numbered terms, at most one leader per term. A follower that hears nothing from the leader for its election timeout increments the term and stands as a candidate; if it collects votes from a majority, it is the leader for that term. Clients then send writes to the leader, which appends the entry to its log, ships it to the followers, and commits once a majority has acknowledged — two message delays, not a fresh election, per write.

The timeouts are where operators get hurt. etcd defaults to a 100 ms heartbeat and a 1,000 ms election timeout, and the rule of thumb is that the election timeout must exceed the round-trip time between members by a comfortable margin. Set it below the real round trip and the cluster elects a leader, fails to hear from it in time, elects another, and never commits anything: a cluster that is up, healthy, and permanently making no progress.

Raft also handles the case that makes naive voting fail. If several followers time out together they split the vote and no one wins — so each waits a randomly chosen interval before standing. The randomisation is not a polish detail; it is the mechanism by which the protocol escapes ties.

The cost is one round trip, and it is set by geography

A decision cannot be final before a majority has heard about it, so every commit costs at least one network round trip to the nearest majority. No implementation improves on this, because it is the speed of light.

Light in fibre travels roughly 200,000 km/s. New York to London is about 5,600 km, so the round trip cannot beat 56 ms, and real links measure nearer 70. A single key replicated across those two cities therefore supports on the order of 18 sequential dependent updates per second — with infinitely fast computers and perfect software. Inside one data centre the same round trip is well under a millisecond, and the same protocol does tens of thousands.

The word sequential carries the weight. Consensus protocols pipeline entries that do not depend on each other, so cluster throughput is far higher than one commit per round trip. What the round trip fixes is the latency of a single decision, and therefore the rate at which you can make decisions that each depend on the last. A design that puts a global consensus group in the path of every user action has bought that 56 ms for every action.

You cannot have both safety and guaranteed progress

In 1985 Fischer, Lynch and Paterson proved that in a fully asynchronous system — no bound on message delay — no deterministic protocol can guarantee agreement if even one process may crash. Not "no efficient protocol": none, ever. The proof turns on the ambiguity from the Definition, that a crashed process is indistinguishable from a slow one.

Every real protocol lives with this by splitting its promises in two. Safety — never decide two different values — is unconditional and holds under any delay, any partition, any number of crashes. Liveness — actually decide something — is conditional, and holds only when the network behaves well enough for a leader to survive its heartbeat interval. So a Raft cluster whose network is flapping does not corrupt itself; it stops. When someone says a consensus protocol "handles" asynchrony, this is what they mean: it declines to make progress rather than declining to be correct.

Types

The two axes that separate the families are what a faulty participant may do, and whether the decision is final immediately or only in probability.

1. Leader-based, crash-tolerant. Multi-Paxos, Raft, Zab (ZooKeeper's protocol) and Viewstamped Replication. A fixed, known membership; participants may crash and recover but never lie; 2f+1 machines. This is what runs inside virtually every cluster manager and distributed database.

2. Leaderless. EPaxos and generalised Paxos remove the leader bottleneck by observing that commands which commute — writes to unrelated keys — need no agreed order between them, and can commit in a single round trip to the nearest majority rather than a round trip to a leader that may be on another continent. The gain is real for geo-distributed deployments and the complexity is substantially higher, which is why adoption has been narrow.

3. Byzantine, with immediate finality. Castro and Liskov's PBFT (OSDI 1999) was the first protocol to tolerate arbitrary — lying, contradictory, actively malicious — behaviour at speeds usable in a real system, and it needs 3f+1 participants. Its cost is quadratic: every replica talks to every other, O(n²) messages per decision, rising to O(n³) when a leader must be replaced, which is why it does not scale past roughly a hundred nodes. HotStuff (2018) brings the steady state and the leader change down to O(n) using threshold signatures, at the price of a third round trip; it and Tendermint underpin most permissioned blockchains.

4. Byzantine, with probabilistic finality. Nakamoto consensus, as used by Bitcoin, drops the assumption that membership is known. Without a fixed roster there is no quorum to count, so agreement is bought by making history expensive to rewrite rather than by taking a vote. The consequence is that a decision is never strictly final, only exponentially unlikely to reverse — hence waiting for six confirmations, about an hour, instead of the millisecond finality a Raft commit gives.

The jump between families 1 and 3 is the number worth remembering. Surviving one crashed machine takes 3 replicas; surviving one lying machine takes 4. Two faults: 5 against 7. Three faults: 7 against 10. A crashed machine only ever goes silent, so the honest majority sees one consistent story; a Byzantine machine can tell different lies to different peers, so the honest participants must outvote the liars and reconcile contradictory testimony. That extra f is the price of the second requirement, and it is why a bank's internal database runs Raft on five nodes while a public chain, whose participants are strangers, spends orders of magnitude more to settle the same kind of question.

Real-World Applications

Kubernetes is a Raft cluster with a scheduler attached. All cluster state lives in etcd, and every write — creating a deployment, updating a pod's status, renewing a lease — is a Raft decision. The operational consequences follow directly from the table above: a three-member etcd survives one machine, a five-member survives two, and losing the majority does not merely slow the cluster down, it makes the control plane read-only until a human intervenes. Running workloads continue, but nothing can be scheduled, scaled or repaired.

Chubby put consensus behind an interface so that other teams would stop reimplementing it. Google's lock service (OSDI 2006) wrapped Paxos in a small file-and-lock API; the paper's most quoted observation is that developers reached for it having never realised they needed distributed consensus at all, because "elect a primary" and "store a small amount of critical metadata" are how the need actually presents itself. ZooKeeper became the open equivalent and spent a decade under Hadoop, HBase and Kafka.

Kafka's replacement of ZooKeeper shows what the dependency costs. Rather than run a second consensus cluster alongside the brokers, Kafka moved its metadata into its own Raft implementation, KRaft. Apache Kafka 4.0, released 18 March 2025, removed ZooKeeper support outright — not deprecated, removed — so a Kafka cluster is now one distributed system to operate instead of two.

Sharded databases run many small consensus groups, never one big one. Spanner, CockroachDB, TiDB and YugabyteDB all partition data into ranges and give each range its own Paxos or Raft group of three to five replicas. Write throughput then scales with the number of ranges, because independent groups commit in parallel; a single group spanning all the machines would scale negatively. This is the standard answer to the "adding nodes makes it slower" problem, and it is worth knowing before you design anything around a replicated log.

Multi-agent AI systems are re-encountering the problem without the vocabulary. When several agents must settle on one plan, or when a multi-agent system votes on an answer, the shape is agreement among unreliable participants — with the extra difficulty that a language model is non-deterministic, so two honest agents given the same information can legitimately return different answers. The classical failure models below do not have a box for that.

Key Concepts

• Safety is unconditional, liveness is not. Any claim that a protocol "guarantees consensus" should be read as: it guarantees it will never decide two things, and it will decide one thing once the network cooperates. FLP says you cannot promise more.
• Terms and epochs are fencing tokens. Every leader is stamped with a monotonically increasing number, and messages from an older number are rejected on sight. This is what stops a leader that was paused for thirty seconds from resuming and writing as though nothing happened — the same fencing pattern that storage systems use to reject a stale writer.
• Consensus is not the same as replication. Copying data to three machines is replication; that they agree on the order the writes were applied is consensus. You can have the first without the second, and the result is three machines with three different histories.
• The log must be trimmed or it eats the disk. A replicated log grows forever, so every implementation snapshots state and discards the prefix — and then needs a way to bring up a member so far behind that the entries it needs are gone. Snapshot transfer is unglamorous and is a reliable source of production incidents.
• Membership changes are part of the protocol, not an admin task. Adding or removing a machine changes what "majority" means, and if two configurations are ever live at once they can form disjoint majorities and decide differently. Raft's joint-consensus step exists solely to make the transition atomic.

Challenges

Adding machines makes writes slower, always. Each additional member adds messages to every decision and does not raise the commit rate at all, because commit still waits for a majority. Worse, a larger majority means waiting for a slower machine: with five members you wait for the third-fastest, with nine for the fifth-fastest. Growth comes from partitioning into more groups, as the sharded databases above do, never from enlarging one.

A geo-distributed group inherits its slowest leg on every write. Placing replicas in three continents for disaster tolerance means each commit waits for the second-nearest, and the 56 ms figure above stops being a curiosity and becomes your write latency. Teams that need both usually pin the leader near the traffic and accept that failover to another region costs a latency step change, or restructure so that most operations touch a single region's group.

Losing the majority is a manual, dangerous recovery. Two of three members gone and the cluster is read-only by design. The tools to force a new configuration from a single survivor exist, and using them means asserting that the missing machines are truly gone — because if they come back having committed entries the survivor never saw, the protocol's core guarantee has been broken by hand. Operators reach for this in an outage, under time pressure, which is the worst possible circumstance for a decision that cannot be undone.

Implementations are much harder than the papers. The published protocol is the easy part; log compaction, membership changes, client session semantics and disk-corruption handling are where correctness is actually lost, and bugs in this layer surface only under precise message interleavings. The field's settled advice is unambiguous: use etcd, ZooKeeper or an established library, and do not write your own.

Not every problem needs agreement, and finding out costs a round trip either way. Coordination is the most expensive thing a distributed system does, so the largest wins usually come from arranging not to need it — the direction distributed computing takes with conflict-free data types and causal consistency, where replicas converge without ever taking a vote.

Future Trends

Byzantine tolerance is leaving cryptocurrency. HotStuff's linear message complexity made 3f+1 agreement cheap enough to consider outside a blockchain, and the interest now is in settings where the participants are separate organisations that trust each other's software but not each other's incentives — clearing between banks, shared industry ledgers, cross-cloud coordination. The protocols are the same; the trust assumption is what changed.

Leaderless and flexible quorums are the answer to geography. Flexible Paxos observed that the election quorum and the replication quorum need only intersect with each other, not each be a majority, which lets a deployment trade a cheaper common case against a costlier leader change. Combined with EPaxos-style commutativity, this is the main direction for systems that must serve writes on several continents without paying a cross-ocean round trip for each one.

Hardware is shrinking the round trip, but only locally. RDMA and kernel-bypass networking cut intra-data-centre round trips into the single-digit microseconds, which moves the bottleneck for a local consensus group from the network to durable storage and the protocol's own message handling. None of it helps between continents, where the constraint is physics rather than engineering, so the gap between local and global agreement is widening rather than closing.

Code Example

Two properties, computed rather than asserted: that majorities always overlap, and what the speed of light permits.

from itertools import combinations

def majority(n: int) -> int:
    return n // 2 + 1

def all_quorums_overlap(n: int) -> bool:
    """The one fact consensus rests on, checked by brute force."""
    q = majority(n)
    return all(set(a) & set(b)
               for a, b in combinations(combinations(range(n), q), 2))

for n in (3, 4, 5, 6, 7):
    q = majority(n)
    print(f"N={n}  quorum={q}  tolerates {n - q} crash(es)  "
          f"quorums overlap: {all_quorums_overlap(n)}")

def sequential_decisions_per_second(km: float) -> float:
    """Ceiling from the speed of light in fibre (~200,000 km/s), nothing else."""
    return 1 / (2 * km / 200_000)

for name, km in (("same metro", 50), ("US coast to coast", 4100), ("NY-London", 5600)):
    print(f"{name:>18}: {sequential_decisions_per_second(km):>7,.0f} decisions/s ceiling")

# N=3  quorum=2  tolerates 1 crash(es)  quorums overlap: True
# N=4  quorum=3  tolerates 1 crash(es)  quorums overlap: True
# N=5  quorum=3  tolerates 2 crash(es)  quorums overlap: True
# N=6  quorum=4  tolerates 2 crash(es)  quorums overlap: True
# N=7  quorum=4  tolerates 3 crash(es)  quorums overlap: True
#         same metro:   2,000 decisions/s ceiling
#  US coast to coast:      24 decisions/s ceiling
#          NY-London:      18 decisions/s ceiling

The first block is the whole safety argument, and note that it does not depend on n being odd — even clusters are safe, merely wasteful. The second block is why nobody has shipped a fast global database: 18 decisions per second is not a limit of anyone's code, and no release will raise it.