Consensus Algorithms Compared: Paxos, Raft, ZAB, and PBFT

Most engineers meet consensus algorithms in the wrong order: first the problem (“the cluster must agree”), then a menu of names (Paxos, Raft, ZAB, Viewstamped Replication, PBFT) each defended by people who remember a different decade of distributed systems research. The comparison is worth doing carefully, because the families differ in fault model, in cost, and in the kind of system they belong inside. The problem itself, and the majority arithmetic behind every one of them, was fixed in distributed consensus; this article is about the algorithms.

One framing carries the whole comparison: safety always, liveness with assumptions. Every family below preserves agreement in every execution (crashes, partitions, adversarial delays included) and each pays for progress with a different assumption about timing or trust. What separates them is the fault model they assume, the machinery they use, and how much of that machinery a maintainer can hold in their head at once, all of it riding on the same distributed systems substrate of partial failure, unreliable messaging, and no shared clock.

Consensus algorithms are protocols in which a set of nodes agree on a single value (or, deployed, on an ordered log of values) using majority quorums to tolerate some number of failures without breaking agreement, validity, or termination.

What a consensus algorithm must deliver

The bar, set in the previous article: agreement (no two correct nodes decide differently), validity (the decided value was proposed by someone), termination (correct nodes eventually decide), all while nodes crash and the network delays, drops, duplicates, and reorders traffic. Two dimensions sort the families compared below.

The first is the fault model. Three of the four tolerate crash faults (nodes that stop, but never lie) and need 2f+1 nodes to tolerate f failures, because majorities of that configuration always intersect. The fourth targets byzantine faults (nodes that keep answering, wrongly) and pays 3f+1 nodes for the same f, because its quorums must be guaranteed to overlap in an honest node.

The second is deployment shape. Some families are foundations inside other systems: Paxos inside Spanner and Chubby, Raft inside etcd and CockroachDB. One is a complete coordination service with the algorithm welded in: ZAB inside ZooKeeper. One is a specialized protocol for trustless settings. In practice that second dimension decides more often than the first; the realistic choice is usually which system to adopt, not which algorithm to implement.

Paxos: the classic

Paxos, published by Leslie Lamport in “The Part-Time Parliament” (1998) and clarified in “Paxos Made Simple” (2001), solves consensus on a single value with three roles: proposers propose values, acceptors vote on them and remember, learners record the outcome. A decision runs in two phases. In the first, a proposer asks a majority of acceptors to promise they will ignore all older proposals; in the second, it submits its value to a majority and collects acceptances. Ballot numbers keep competing proposals ordered, and majority overlap does the safety work: any two majorities share an acceptor, so a value already accepted by one majority is carried forward into every later proposal that could possibly win.

Deployed systems do not run one-decree Paxos; they run Multi-Paxos: a stable leader processing a sequence of values, skipping the first phase on the strength of promises already collected. Lamport’s papers describe this as an optimization. In practice it is the whole system, and the gap between the two is where implementations diverge: Multi-Paxos is less a single algorithm than a family of engineering decisions each implementer made alone.

Two things made Paxos famous. One is the mathematics: the core protocol is small, minimal, and correct, and it defined the field. The other is difficulty; Lamport opened “Paxos Made Simple” by conceding the original description had defeated many of its readers, and the paper that followed is one of several attempts to make Paxos explicable. The definitive production account, Google’s “Paxos Made Live” (2007), describes what a team building Chubby discovered: the published algorithm is a proof, not a blueprint, and a deployable system around it requires substantial additional machinery that no paper specified. Paxos’s descendants inherited both the correctness and the implementation risk.

Raft vs Paxos

Raft’s design brief was understandability, not novelty. In “In Search of an Understandable Consensus Algorithm” (Ongaro and Ousterhout, 2014), the authors started from Multi-Paxos and reworked every mechanism they found hard to explain, then evaluated the result partly by how long students needed to answer questions about it. The differences that came out of that process:

• A strong leader. In Raft, all log entries flow one way (client to leader to followers) and the leader decides entry order unilaterally. Paxos permits any proposer to drive progress, which is more flexible and more chaotic. Raft traded the flexibility for a normal case a maintainer can follow on a whiteboard.
• Leader election built in. Raft elects its leader with randomized timeouts, as part of the algorithm. Paxos specifies no leader at all; Multi-Paxos systems bolt on an election mechanism of their own design, which is a recurring source of divergence between implementations.
• An explicit log. Raft specifies the replicated log end to end: entry format, the consistency check on append, conflict resolution, the commit rule. Paxos decides values and leaves the log as an exercise, and each implementation’s answer to that exercise is another thing no two deployments share.
• Membership changes specified. Raft defines how the cluster itself changes: one server at a time, or through joint consensus over two configurations. The Paxos literature leaves reconfiguration largely to the implementer.

Under the differences, the two are closer than the rhetoric suggests. Both decide through majorities; both rest correctness on quorum intersection; a Raft term is a ballot, a Raft leader is a Multi-Paxos leader with extra specification. Neither is more correct, both are proven safe, and both buy liveness with the same partial-synchrony assumptions. The honest comparison is about the implementer: which one will a team implement, verify, and modify correctly for years? The industry’s answer over the last decade has been Raft (etcd, Consul, CockroachDB, TiKV, and Kafka’s KRaft mode all replicate through it) while Paxos lives mostly inside long-established systems such as Chubby and Spanner, where it is proven, staffed, and already paid for.

ZAB: ZooKeeper’s algorithm

ZAB (ZooKeeper Atomic Broadcast) is the protocol inside ZooKeeper, described alongside the system itself (Hunt et al., 2010) and formally in Junqueira and Reed’s 2011 paper. It is a broadcast protocol for a primary-backup architecture: a single primary orders every update, every server applies updates in exactly that order, and the ordering guarantee (total order across all updates, with no update delivered ahead of its predecessors) is what ZooKeeper’s coordination API is built on.

ZAB’s distinguishing emphasis is crash recovery. Its protocol runs in phases that exist for the moment a cluster re-forms after losing its primary: discovery locates the current epoch and the server with the most recent history, synchronization aligns every follower to that history, and only then does broadcast resume. Where Raft’s specification optimizes for an engineer implementing the algorithm, ZAB’s phases optimize for a coordination service that must come back consistent after every failure, and its zxids (epoch numbers joined to per-epoch counters) do the work Raft assigns to terms and log indexes.

In a comparison table ZAB and Raft sit close: crash faults, 2f+1 arithmetic, a strong leader, epoch-style ordering, recovery that repairs history before resuming. The practical difference is heritage. ZAB was designed as the heart of one system, born at Yahoo! and central to the Hadoop ecosystem for over a decade; Raft was designed as a general-purpose algorithm for other people to implement. That shows up in who runs each today: ZooKeeper deployments run ZAB because ZooKeeper does; new systems overwhelmingly choose Raft when they choose at all.

Byzantine fault tolerant consensus

All three families so far assume nodes fail by crashing: they stop, or stall, but never answer wrongly. When the threat model includes lying: misbehaving software, corrupted memory, or participants belonging to someone else; the problem becomes byzantine fault tolerant consensus, and the arithmetic changes. The reference protocol is PBFT (Castro and Liskov, 1999): 3f+1 replicas tolerate f byzantine faults, because its quorums of 2f+1 must overlap in a number of nodes too large for f of them to be liars.

PBFT’s normal case runs three phases of all-to-all exchanges (pre-prepare, prepare, commit) so each honest replica can confirm that every other honest replica saw the same request and reached the same prepared state before anyone commits. View change replaces a faulty or slow primary. The cost is message traffic that grows with the square of the cluster size, and the prize is agreement despite answers that are actively wrong; something no crash-fault protocol can offer at any cluster size. Permissioned blockchain networks run protocols in this family; Tendermint, a byzantine consensus protocol descended from PBFT’s design, rotates its proposer every block and is the consensus engine behind the Cosmos ecosystem of chains. For a single organization’s systems, where nodes belong to one trust domain, the byzantine machinery is a cost without a customer; crash-fault consensus plus operational controls is the fit.

Choosing a consensus algorithm

The realistic decision usually sits one level up. Teams rarely pick an algorithm from a menu; they adopt a system that contains one (etcd, Consul, and ZooKeeper are finished coordination services) and the algorithm inside came with the system. For the cases where the choice is genuinely yours:

Three rules compress the table. Adopt before you implement: a finished coordination service covers most needs, and implementing consensus from a paper is a documented way to rediscover other people’s bugs. If implementation is genuinely required (a storage engine embedding its own replication, for instance) Raft’s understandability is the practical argument, because the hard part is not proving the algorithm correct but keeping a team’s modifications correct for years. Reserve byzantine tolerance for the case that demands it, and decide it by trust boundaries: PBFT’s traffic and its 3f+1 footprint are a tax paid for a trust model most systems inside one organization do not have.

Common mistakes

• Choosing by pedigree. “Google uses Paxos” is a fact about Google’s history, not a recommendation for yours. Spanner’s Paxos groups and a five-node coordination service for a web application are different problems at different scales.
• Comparing Raft to one-decree Paxos. The deployed comparison is Raft against Multi-Paxos. Rating Raft against the 1998 single-value protocol stacks a finished log system against a proof.
• Reaching for byzantine tolerance by default. 3f+1 sizing and quadratic message traffic buy safety against lying nodes. Inside one trust domain, the live threat is crashes and pauses, the crash-fault families.
• Assuming the algorithm is the system. Every family specifies agreement, not monitoring, snapshotting, backup, membership tooling, or upgrades. The gap between algorithm and service is where the engineering effort actually goes, and “Paxos Made Live” remains the canonical tour of that gap.
• Skipping the liveness fine print. Each family’s progress guarantee rests on timing or suspicion assumptions, and operations inherits them as timeout tuning. A deployment that ignored the fine print meets it later as flapping leaders.

FAQ

Which consensus algorithm should I use?

Almost always one that is already inside a system: etcd, Consul, or ZooKeeper for coordination, a strongly consistent database for storage. Implementing from scratch is justified mainly when a product embeds its own replication, and in that case Raft (implemented and maintained across etcd, CockroachDB, TiKV, and Kafka’s KRaft) is the default answer.

Is Raft better than Paxos?

Neither is more correct, both are proven safe, and both buy liveness with similar timing assumptions. Raft was designed to be understood and maintained, and it specified the log, election, and membership that Multi-Paxos leaves to implementers, which is why new implementations cluster around it. Paxos remains the foundation of long-running systems such as Chubby and Spanner, where a rewrite to Raft would be risk without benefit.

Why does byzantine consensus need 3f+1 nodes?

Its quorums must overlap in enough honest nodes to outnumber the liars. With 3f+1 nodes and quorums of 2f+1, two quorums intersect in at least f+1 nodes, more than the f that could be byzantine, so at least one honest witness sits in every overlap. With only 2f+1 nodes the overlap could be entirely byzantine, and safety would depend on trusting liars.

Is ZAB the same as Raft?

The same shape, not the same algorithm. Both use a strong leader, 2f+1 quorums, and epoch-style ordering, and both repair history after a leader fails. ZAB runs in explicit recovery phases designed inside ZooKeeper; Raft specifies log replication and membership for general implementation. Systems rarely choose between them, they inherit ZAB with ZooKeeper and adopt Raft when building new.

Is consensus the same as two-phase commit?

No. Two-phase commit makes separate participants agree on one transaction outcome, and it blocks if the coordinator dies mid-flight. Consensus decides among proposals using majority quorums and stays available through failures, which is why coordinator high availability is often built as a consensus group behind the commit protocol. Distributed transactions covers the mechanics.

Related articles

• Next read: the Raft consensus algorithm: leader election, log replication, and safety, in depth.
• distributed consensus: the problem these families solve, and the quorum arithmetic they share.
• the Paxos algorithm: the classic and Multi-Paxos, covered properly.
• leader election; the application consensus is most often asked to perform.
• distributed locks: leases and fencing tokens, coordination’s everyday face.