Introduction
Consensus in a distributed system is the agreement of multiple nodes on a common decision or order of operations, which persists despite node failures and network latency. The problem seems trivial until it becomes clear that a node can't distinguish a downed neighbor from a slow one, and the network is entitled to deliver a message an hour after sending.
Paxos, Raft, and Zab diverge in almost everything: the roles of nodes, the method for electing a leader, and what happens after a failure. They share one requirement: decisions must be made by a group of nodes. Any two such groups must overlap, and the simplest way to guarantee this is a majority. Everything else stems from this requirement, including the differences between etcd, ZooKeeper, and Consul, which, while sharing a common foundation, provide different read guarantees for different clients.
Paxos: what safety costs
Paxos is a basic consensus algorithm that guarantees a single decision (a single value) in an asynchronous network even if nodes fail, as long as at least a majority remains operational. Paxos operates with three node roles-proposers, acceptors, and learners-which can coexist on the same servers. Proposers propose values, acceptors vote on them, and learners learn the outcome of their decisions. A key property of Paxos is safety: it guarantees that two different nodes will not reach different decisions, even if messages are lost or nodes are rebooted. However, liveness is only possible when a quorum of nodes is available and there is no endless duel between proposers.
This limitation has a rigorous justification. The FLP theorem (Fischer, Lynch, Paterson, 1985) proves that in a fully asynchronous network, where there is no upper bound on message latency or node speed, a deterministic consensus algorithm cannot guarantee termination even if a single node fails. This is due to indistinguishability: the receiver is unable to distinguish a downed node from a very slow one, and any finite latency is arbitrary.
Paxos overcomes this by separating its guarantees. Safety holds unconditionally, regardless of delays and message losses: two nodes will never commit to different decisions. Progress, however, is guaranteed only when the network behaves sufficiently predictably—that is, in a model of partial synchrony. This is the origin of dueling proposers: two nodes can take turns bidding on each other with increasingly higher numbers, each time wiping out the other's work. The protocol itself doesn't protect against this, in practice, the problem is solved with a dedicated leader and a randomized delay before retrying, so that proposers don't start synchronously.
Partial synchrony isn't the only way out of FLP. A second option is to abandon determinism. Randomized protocols like Ben-Or flip a coin where a deterministic algorithm stalls and terminate with probability 1, but with no upper bound on the number of rounds. The "almost certainly someday" guarantee doesn't hold well for a system that's expected to respond within tens of milliseconds, so timeouts have become the norm in general-purpose infrastructure. Randomization remains in places where timeouts can't be trusted in principle—in Byzantine protocols.
This distinction holds true for all three algorithms in the article. Neither Paxos, Raft, nor Zab overcome FLP, they merely choose differently where to place timeouts and how quickly to converge to a single leader.
Phases of the Paxos and Multi-Paxos protocol
Basic Paxos (sometimes called Single-Decree Paxos) consists of a two-phase protocol with message exchanges between proposers and acceptors. These phases are often referred to as Prepare and Accept:
Phase 1: Prepare. The proposer selects a unique proposal number n that is the highest of all previously used proposals and broadcasts a Prepare(n) request to all acceptors. An acceptor, upon receiving a Prepare with a number higher than any previously seen, responds with a Promise(n) and promises not to accept proposals with a lower number. It also informs the proposer which v_a value with which n_a number it has already accepted, if any.
Phase 2: Accept. After receiving responses from a majority of acceptors (a quorum) in the Prepare phase, the proposer determines the value to accept and has no choice. If at least one acceptor in the quorum has announced a previously accepted value, the proposer must accept the one with the highest n_a number. They may propose their own value only if the quorum has not yet accepted anything. Deviating from this rule breaks safety: a proposal with a higher number will overwrite an already chosen solution. Uniqueness of a solution follows from the intersection of quorums: any two majorities have at least one common acceptor, and an acceptor cannot accept two different values without breaking their promise. If a value has already been chosen, any proposal with a higher number must propose it—this prevents the solution from being lost during a leader change. Therefore, the value selection rule in phase 2 is formulated as an obligation, not an optimization.
For a sequence of decisions (e.g., writing a command log), basic Paxos is applied multiple times for different "slot numbers" in the log. In practice, an optimized Multi-Paxos mode is used, in which, after the initial round, one node acts as the leader (coordinator) for all subsequent writes until a failure occurs. The leader, upon receiving client transactions, acts as the proposer for new values and, thanks to the trust of the acceptors, can skip the Prepare phase for each value, sending Accept requests directly (meaning decisions are made faster, similar to continuous operation with a single coordinator). This achieves efficiency similar to single-leader replication: Prepare phase messages are infrequent until the leader changes.
Paxos does not have a separate election mechanism, and this is a fundamental difference from Raft and Zab. Leadership here occurs de facto: the proposer whose proposal with the highest number has passed the Prepare phase with a quorum becomes the leader. Nothing prevents two nodes from simultaneously claiming the leadership—safety is not affected, only progress. Therefore, all practical implementations of Multi-Paxos build on top of the protocol: they appoint a coordinator administratively, elect it via a failure detector or a separate leadership protocol, and add a lease with a timeout. The standard doesn't specify what exactly to do, and each system decides for itself. This unaddressed gap is the commonly cited "Paxos complexity": the algorithm itself is short, but everything needed around it for a working system is unspecified.
During a network partition, a Paxos system maintains consistency at the cost of availability: a minority of the cluster stops moving, but doesn't write anything inconsistent. The gap between the strict core and the unspecified framework gave birth to Raft—an attempt to describe not only the algorithm, but also everything needed around it for a working system.
Failure Handling and Recovery in Paxos
The Paxos algorithm is resilient to node failures: as long as at least a majority of acceptors are operational, a new value can be selected. If the current leader (the Multi-Paxos coordinator) fails or loses contact, other proposers can initiate new Prepare rounds with a higher proposal number, effectively electing a new leader. Due to the quorum system, the old and new leaders can never each secure a majority of votes simultaneously, so consistency is not compromised. Paxos tolerates long stalls (for example, if less than half the nodes are available, progress is suspended, but the previously reached decision is not reversed). Upon recovery, nodes synchronize their logs based on the accepted values: already committed operations will be delivered from learners or the leader. The protocol requires each acceptor to store on disk its last promised number n_p and the accepted value v_a with the number n_a. This ensures that a node, upon recovery, does not break previously made promises not to vote for "old" proposals. Thus, Paxos ensures data persistence: neither node failures nor arbitrary message delays lead to inconsistencies – the system either extends the choice time or pauses until a quorum is restored, but does not make incorrect decisions.
Paxos pseudocode example
Below is a simplified pseudocode of how the key Paxos roles – proposer and acceptor – work, demonstrating the described phases of the algorithm (based on the classical description):
function proposer(node_id, value):
round = last_round_seen + 1
n = (round, node_id)
send Prepare(n) to all acceptors
# --- Phase 1 ---
wait for Promise/Nack with timeout
if received Nack(n_p_other):
last_round_seen = max(last_round_seen, n_p_other.round)
# otherwise proposers duel forever
sleep(randomized_backoff)
retry
if not quorum_of(Promise):
sleep(randomized_backoff); retry
# --- Value selection ---
# Must reuse an already accepted value, otherwise safety is lost.
accepted = [r for r in promises if r.v_a is not None]
if accepted:
# compare PAIRS, not plain numbers
v = v_a of response with maximal n_a
else:
v = value
# --- Phase 2 ---
send Accept(n, v) to all acceptors
wait for Accepted/Nack with timeout
if quorum_of(Accepted(n)):
send Decided(v) to learners
else:
sleep(randomized_backoff); retry with higher round
# Acceptor - keeps persistent state n_p, n_a, v_a
on receive Prepare(n):
# proposal is newer than anything seen before
if n > n_p:
n_p = n
fsync(n_p)
# report our last accepted value (if any)
reply Promise(n, n_a, v_a)
else:
reply Nack(n_p)
on receive Accept(n, v):
# proposal is not stale
if n >= n_p:
n_p = n
n_a = n
# accept the new value under number n
v_a = v
fsync(n_p, n_a, v_a)
# acknowledge acceptance
reply Accepted(n)
else:
reply Nack(n_p)
This protocol ensures that an acceptor who promised not to accept old numbers will not accept a value from the old leader after seeing a newer proposal. And the proposer, having learned of previously accepted values (via v_a), resubmits them to avoid losing what has already been committed. Ultimately, unanimity is achieved: once a majority of acceptors accept a value, it becomes the decision.
Raft: Same result, but with a clear leader
Raft (Diego Ongaro, John Ousterhout, 2014) was created as a simpler, more understandable alternative consensus algorithm that provides the same properties as Paxos. Raft also belongs to the class of iterative consensus algorithms for a replicated log—that is, it maintains a replicated state machine: all nodes apply the same commands in the same order, ensuring that their state remains consistent. Unlike classic Paxos, Raft explicitly separates subproblems: (1) leader election, (2) log replication, and (3) safety. The core idea of Raft is to always have an explicitly elected leader through which all written changes flow, simplifying the protocol's understanding.
In a Raft cluster, each node can be in one of three states: Follower, Candidate, or Leader. In normal mode, there is a single leader, and the remaining nodes are followers, passively replicating its log. If the leader fails or contact with it is lost, the nodes proceed to elect a new leader. Below is a diagram of node states in Raft and the transitions between them during leader election:
Leader selection in Raft
Raft achieves consensus leader election through rounds of voting called terms. Terms are numbered and stored on each node. At the beginning of the process, all nodes are Followers and have no leader. Each Follower starts a randomly assigned timer (the election timeout). If the timeout expires without receiving a heartbeat message from the leader, the node assumes there is no leader and transitions to the Candidate state, increments its term, and begins electing a new leader. The candidate votes for itself and broadcasts a RequestVote to all other nodes, specifying its term and the index of the last entry in its log. Each node (Follower) receiving this request decides whether to grant or reject the vote, according to the following rules:
The voting Follower compares the candidate's term with its current term. If the candidate's term is lower (outdated), the vote is rejected. If the candidate's term is not lower, the Follower updates its current term and can vote.
Each Follower has the right to vote for only one candidate within a single term (it remembers votedFor = candidateId). Repeated requests from other candidates in the same term are rejected.
A Follower also checks the candidate's "log freshness": it votes only if the candidate's log is at least as up-to-date as its own (based on the index and term of the last entry). This ensures that the candidate with the most advanced log is elected, facilitating subsequent log synchronization.
The candidate that receives the votes of a majority of nodes (quorum > N/2) wins and becomes the new leader (transitions to the Leader state). From this point on, it sends periodic Heartbeat messages (empty AppendEntries RPCs) to all other nodes to notify them of its leadership and prevent new elections. The election can fail in two cases. Either the candidate fails to secure a majority—for example, if the votes are split between several candidates—in which case it waits for a new timeout and begins the next term. Either it has received AppendEntries from the current leader with a term equal to or greater than its own, in which case it returns to Follower and accepts that leader. The use of randomized timeouts prevents repeated split votes—usually, one node will initiate elections first. Raft elections are fast (within about two timeouts) and guarantee that no two leaders can emerge in a single term at any given time (thanks to majority voting and the one-vote rule). Each new term is logged, records of previous terms may be incomplete, but Raft guarantees that they will not affect consistency.
Log replication and write commit
Once a leader is elected, all client requests for state changes flow through it. The leader accepts, for example, a command to "write value X," adds the corresponding entry to its local log, and assigns it the current term and next ordinal index. The leader then sends AppendEntries RPCs to its followers with the new entries. In the AppendEntries request, the leader specifies the previous index and term to ensure consistency. Each follower receiving such a request checks: if its log does not have an entry with the specified previous index and term (i.e., the local log is lagging or contains a conflicting end), the follower rejects the AppendEntries request. This mechanism, along with the log freshness check during voting, ensures log convergence: sooner or later, the logs of all nodes will become identical sequences of commands.
Once a record has replicated to a majority of nodes (the leader has received AppendEntries confirmations from the quorum), the leader can mark it as committed, but only if this record belongs to its current term. Replica count alone does not grant the right to commit. A record inherited from the previous leader cannot be committed by the replica count, even if it is on a majority of nodes, it can still be overwritten by a future leader. Such records are committed indirectly: as soon as the leader has committed at least one record of its term, the entire preceding log prefix is considered committed automatically, as follows from the log-matching property. Therefore, in practice, a new leader immediately after being elected writes an empty no-op record to the log: this unlocks the commit of the inherited tail without waiting for client operations.
A committed record is considered finally applied, the leader executes the command in its state machine and returns the result to the client. In each AppendEntries, the leader also transmits the index of the last entry it committed (commitIndex). After receiving this message, the follower also marks the corresponding entries as committed. Therefore, the moment a record becomes visible varies across nodes, and replication to the majority by itself does not provide linearizability of reads. Raft prioritizes consistency over availability: if there are insufficient nodes for quorum (for example, the network is split and the leader is disconnected from the majority), the leader will be unable to advance commitIndex—the system suspends change processing, preserving the previously achieved consistency. In CAP terms, this is a CP system, but the framework itself is rather crude: it describes behavior only during a partition, and a partition is a rare event. The rest of the time, when the network is healthy, the tradeoff remains, it simply swings between latency and consistency: a quorum of three data centers is consistent, but each write is paid for by an interregional round-trip. PACELC captures exactly this: when partitioning (P), choose between A and C, otherwise (E), choose between latency (L) and consistency (C). The article goes on to explain what decides the other half: ReadIndex versus lease read, sync in ZooKeeper versus reading from a local replica, and Cosmos DB consistency levels.
Reads can be served without appending to the log, but not naively "from the leader": an isolated leader doesn't know it has already been deposed and will return stale data. Linearizable reads require ReadIndex (leadership confirmation via a heartbeat round before replying) or lease read based on limited clock drift, reading directly from a follower is only acceptable if lag is acceptable.
Raft uses a more rigid leadership model than Paxos: the leader completely controls the command flow, and followers do not participate in proposing new values. This makes it easier to understand – the system boils down to classic master-slave replication, supplemented by safe leader reelection in the event of a failure. Raft's log matching property: if two records on different nodes have the same index and term, then the entire log prefix up to that index is guaranteed to match. This is achieved by rolling back conflicting entries on followers: if a record on a follower doesn't match the leader's record in terms of term (meaning that it was previously written under the leadership of another leader who failed to commit it), the leader forces the follower to delete this "orphaned" part of the log and replace it with records from its own log. This restores log consistency.
A consistent log alone is insufficient for correct operation, and this is a common oversight in home-brew implementations. A client sends a command, the leader commits it, and crashes before responding. The client times out and repeats the request to the new leader, and the command is applied a second time. This is harmless for "set X = 5," but not for "debit $100". Raft solves this at the state machine level, not the log level: each client receives a unique identifier and numbers its requests. The state machine stores the number of the last command applied and its result for each client. A repeat request with a number already seen is not applied, the saved response is returned. The log contains both copies of the command, and duplicates are pruned upon application. Session records must be cleared by timeout, otherwise the table grows indefinitely, and expired sessions must be rejected with an explicit error, not silently.
Crash Handling and Recovery in Raft
Raft is designed to remain safe (not to contradict already committed records) even in the face of arbitrary node shutdowns, network delays, or partitions. Fault tolerance is achieved as long as a majority of nodes is operational, i.e., ⌊N / 2⌋ + 1. This is the minimum required condition: two disjoint sets of nodes should not be able to independently make decisions, and the intersection of any two majorities is guaranteed to be non-empty. If the leader fails, detection occurs via a timeout. Followers initiate the election of a new leader, as described. Each node stores the currentTerm and votedFor values on disk, as well as its entire log. This means that a node rebooting does not "forget" who it voted for in a given term, nor does it lose its log records. As noted above, the leader does not commit the records of previous terms based on the number of replicas—only indirectly, by committing the record of its own term. This rule, along with the log freshness check during voting, ensures that the new leader always contains all the records committed by its predecessors. This ensures that the new leader continues from a correct state.
If a node falls behind (for example, due to being unavailable for a long time), the log catch-up mechanism allows it to catch up. The leader specifies prevLogIndex/prevLogTerm in AppendEntries messages for checking. If a lagging follower is desynchronized, it will receive an AppendEntries rejection. The leader will decrease prevLogIndex until it finds a common point with the follower's log. If the leader has already discarded the necessary records while compacting its own log, finding a common point is impossible, and then InstallSnapshot is sent instead of AppendEntries (see below for log compaction).
Raft includes a built-in log compaction mechanism. Snapshots are created independently by each node: they are not a leader operation and are not a consensus decision. A node takes the current state of its machine, writes it to disk along with the index and term of the last record included in the snapshot, and then discards the entire preceding log prefix. The node itself chooses the moment to take the snapshot, usually based on the log size. This prevents unbounded log growth and speeds up node restarts: it restores from its snapshot rather than replaying the log from scratch.
If the records needed by the follower have already been discarded, the leader sends it an InstallSnapshot RPC: its entire snapshot (in chunks, if necessary), after which the follower replaces its state with it and continues receiving regular AppendEntries.
Raft also defines a procedure for safely changing cluster membership through joint consensus: it introduces a transitional configuration, C_old,new, in which each decision requires a majority in both the old and new membership—not a larger majority over the union of the two, but two independent majorities. This eliminates the possibility of two leaders emerging during the transition. After committing C_old,new, the leader commits C_new, and the old configuration is removed from play. In practice, the simpler mechanism from Ongaro's dissertation is more commonly used: adding or removing exactly one node at a time, in which the majorities of the old and new configurations overlap automatically and a transition configuration is not required.
As a result, Raft provides developers with a relatively simple model: a single leader replicating commands to followers. It guarantees the linearizability of operations (when using ReadIndex or lease read) and maintains availability in the event of failure of up to ⌊(N−1)/2⌋ nodes, meaning a 3-node cluster survives the failure of one, a 5-node cluster survives the failure of two, and a 7-node cluster survives the failure of three.
This leads to a practical consequence: an even number of nodes does not provide a gain. A 4-node cluster requires a quorum of 3 and therefore survives the failure of only one node—exactly like a 3-node cluster, but each write must reach more replicas, and the probability of at least one node failing is higher. Therefore, Raft clusters are almost always deployed with odd numbers: 3, 5, or 7 nodes. More than 7 are rarely used: fault tolerance increases slowly, and commit latency is determined by the slowest quorum node. Raft implementations demonstrate throughput in the order of thousands to tens of thousands of operations per second per cluster, depending on the workload and hardware. The performance is usually limited by the fsync speed on the leader disk and the network latency to quorum, rather than by the properties of the algorithm itself.
Raft implementation example (code snippet)
class RaftNode:
def __init__(self, node_id, storage):
self.node_id = node_id
self.storage = storage
# --- persistent state ---
self.current_term = 0
self.voted_for = None
self.log = []
# --- volatile ---
self.state = "follower"
def _persist(self):
self.storage.save(current_term=self.current_term,
voted_for=self.voted_for)
self.storage.fsync()
def _last_log(self):
if not self.log:
return (0, 0)
return (len(self.log), self.log[-1].term)
def _step_down(self, term):
self.current_term = term
self.voted_for = None
self.state = "follower"
def _log_is_up_to_date(self, cand_index, cand_term):
my_index, my_term = self._last_log()
if cand_term != my_term:
return cand_term > my_term
return cand_index >= my_index
# ---------- RPC ----------
def on_request_vote(self, term, candidate_id, last_log_index, last_log_term):
term_changed = False
# 1. Stale term - reject. Always return our own term
# so the candidate can step down on its own.
if term < self.current_term:
return (self.current_term, False)
# 2. Term is higher than ours - adopt it and RESET voted_for
# BEFORE checking whether we may vote. Skipping the reset here
# is the classic bug: the node would refuse every candidate
# of every future term forever.
if term > self.current_term:
self._step_down(term)
term_changed = True
# 3. Grant the vote if we haven't voted in this term yet
# (or this is a repeat request from the same candidate)
# and the candidate's log is not behind ours.
granted = False
if (self.voted_for in (None, candidate_id)
and self._log_is_up_to_date(last_log_index, last_log_term)):
self.voted_for = candidate_id
granted = True
self.reset_election_timer()
# 4. Persist before replying over the network if anything changed.
if term_changed or granted:
self._persist()
return (self.current_term, granted)
Zab: A protocol written for a single product
Zab (ZooKeeper Atomic Broadcast) is a consensus protocol developed specifically for the Apache ZooKeeper system. Zab is designed to provide atomic (indivisible) message broadcasting with total ordering and fault tolerance. This means that all ZooKeeper nodes apply all transactions (state changes) in the same order, resulting in identical states. Zab is similar in purpose to Paxos, but is designed as a highly specialized master-replication (primary-backup) protocol with an emphasis on ease of implementation in a production product. It predates Raft by several years, solving the same problem with Multi-Paxos independently. It uses a model with a single leader (primary) and a set of followers—the same design later independently developed by Raft. Zab operates in four phases, and it's worth distinguishing them, as they are often conflated in descriptions. Leader Election: nodes agree on who will be the leader. Discovery: the elected leader collects the quorum's most recent epochs, calculates a new one, and ensures that the quorum accepts it. Synchronization: the leader aligns the followers' logs with its own: it sends missing data and forces them to roll back unnecessary data. Only then does Broadcast: client requests are accepted. The first three phases are collectively called recovery. In the ZooKeeper implementation, Discovery and Synchronization are partially merged, but logically they are distinct steps: the former establishes an epoch, the latter aligns the history. As long as the cluster has a leader and a quorum of living nodes, all client operations sequentially pass through the leader and are distributed to followers.
Recovery: Elections, Epoch, Synchronization
The process of starting or restoring a cluster begins with an election. ZooKeeper uses FastLeaderElection for this: nodes exchange votes and compare candidates using the tuple (epoch, zxid, sid)—epoch first, then the latest zxid if there's a tie, and only if the history is completely identical does the node with the higher ID win. Ultimately, the node with the most complete history in the quorum becomes the leader, and the sid is needed only to resolve ties deterministically. The strict maximum requirement distinguishes Zab from Raft, where a "no worse" log is sufficient—we'll return to this below. After the election, one node becomes the leader, and the others become its followers.
Discovery: Epoch Establishment. The leader doesn't immediately begin accepting operations—it must first secure a new epoch. It collects the followers' last known epochs (the CEPOCH message), takes the maximum, increments it by one, and broadcasts the result back (NEWEPOCH). A follower who accepts a new epoch thereby commits not to accept anything from leaders of previous epochs. Once a new epoch has been accepted by a quorum, the previous leader, even if still alive and unaware of their resignation, can no longer commit, their proposals will be rejected as obsolete.
This is exactly the same work performed by the Prepare phase in Paxos. The difference is in frequency: Paxos runs it for every value (except for optimized Multi-Paxos), while Zab runs it once per leader change.
Synchronization: Log Alignment. Only now does the leader consolidate the quorum's history. Each node stores the latest zxid—a transaction identifier consisting of the epoch number and a counter within it. The leader requests each follower's zxid and checks it against its own log:
If a follower is missing any transactions, the leader sends it the missing log records to bring it up to its latest transaction.
If a follower has "extra" records (with higher zxid values, possibly resulting from the previous leader not having time to commit these records), the leader instructs the follower to roll back these unconfirmed changes. This is necessary because, since they weren't previously committed by the majority, they shouldn't affect the system's state after recovery.
When the leader and follower reach the same latest zxid value, the leader includes this follower in the synced state. Having gathered a quorum of such followers, it broadcasts NEW_LEADER, a signal that the history is aligned and ready to proceed. From this point on, all followers in the quorum have the same history prefix, and the leader proceeds to the broadcast phase.
The order here is not arbitrary. First the epoch, then the logs—because rolling back someone else's records is a destructive operation, and permission to do so must be obtained in advance. If a leader began reconciling history before a quorum had recognized its epoch, it could delete transactions from followers and then be abandoned—and the data already reported to the client would disappear. Recognizing the epoch by a quorum ensures that subsequent events won't be undone by an older leader.
Atomic broadcast
In the broadcast phase, the current leader accepts client requests (transactions, such as changes to ZK nodes) and distributes them to all followers. Each new request receives a unique incrementing zxid (consisting of the leader's epoch number and a counter). The leader sends a proposal with this zxid to all followers (essentially a record of the transaction). Followers, having received a proposal, record it in their log and send an acknowledgment (ACK) to the leader. When the leader collects ACKs from a quorum of nodes, it sends a commit command to everyone for that zxid - from that moment on, the transaction is applied to everyone. Structurally, this is half of Paxos: proposal plays the role of an Accept request, and the Prepare phase is not needed, because the leader has already set its epoch during the recovery phase - just like Multi-Paxos skips Prepare until the leader changes. There is no separate message about a commit in basic Paxos, notification to learners is not considered part of the protocol, in Zab this is an explicit step. In ZooKeeper, all changes go through this negotiation, which ensures a linear order: if one transaction A was sent before B and confirmed, then all nodes will apply A before B. The leader takes care of this by ordering outgoing proposals, and the overall confirmation queue is maintained by a quorum requirement.
Zab guarantees reliable delivery (every transaction confirmed by the leader will reach all correct nodes) and total order of delivery. In addition, the causal order is respected: if transaction B is sent after the delivery of A on the same originator node, then B will be ordered after A. These guarantees correspond to the semantics of ZooKeeper: all nodes see changes in the same order, and a client sequentially sending requests sees them in the order they were sent.
Why ZooKeeper didn't take Paxos
The obvious question is: why write your own protocol when Multi-Paxos solves the same problem? The answer is that ZooKeeper needs a guarantee that Paxos doesn't provide.
Paxos ensures consensus on each log slot independently. Slots can be filled in any order, and one leader is free to begin work on slot 5 without waiting for the outcome of slot 4. For a database that issues commands when the entire prefix is ready, this is fine. For ZooKeeper, it's not: its transactions are incremental and written relative to state. Writing "increment znode /config version from 7 to 8" is only meaningful if the state is actually at version 7. Swap two such transactions or lose one in the middle, and the result won't be "slightly different," it'll be meaningless.
Therefore, Zab requires primary order—two conditions beyond the usual total order. First, a leader's proposals are delivered in the order in which they issued them, with no gaps in the middle. Second, if the leader of epoch e could have seen a transaction—that is, it was proposed in an epoch earlier than e and is potentially visible—then it is ordered before anything the leader proposes. To meet this second requirement, the Discovery phase elects the node with the highest zxid as the leader and forces the other nodes to roll back any tails the leader doesn't have.
This explains the difference in the election rules. Raft votes for a candidate whose log is "no worse" than the voter's log, and allows for the less advanced node to win, as long as it contains all committed records, it will simply overwrite any missing ones later. Zab requires the leader to have the highest zxid among the quorum and moves the alignment to a separate phase before work begins. Both approaches are safe, but they distribute work differently: Raft switches to servicing clients faster and aligns logs on the fly, while Zab does this in advance.
Fault Tolerance and Recovery in Zab
The recovery mechanics are discussed above, but the practical result is this: a transaction caught by the leader's failure is either recovered if it has reached the majority, or discarded. The monotonically increasing epoch number within zxid plays the same role as a term in Raft and a proposal number in Paxos: it prevents the previous leader from interfering with the new leader.
Zab was written for a specific implementation, and this is evident in the details. The leader writes the transaction to disk before sending a proposal, not after—otherwise, it could confirm to the client something it wouldn't survive. Proposals and ACKs are batched: under high load, a single fsync can process dozens of transactions, and throughput in practice is determined by this batching. The flip side of that specialization is its narrowness. Zab assumes a single leader and a full replica on each node, and is rarely encountered outside of coordination services: it's a single-product protocol, not a reusable component.
Comparison table of algorithms
The three protocols solve the same problem and differ in the payment method. Let's summarize the differences discussed above, and then we'll discuss where each is applied in practice.
| Paxos (Multi-Paxos) | Raft | Zab | |
|---|---|---|---|
| Leader election | No mechanism, leadership is de facto, left to the implementation | Term-based voting, randomized timeouts | FastLeaderElection, a separate phase |
| Leader requirement | Any proposer that completed Prepare on a quorum | Log no less up-to-date than the voter's | Strictly highest zxid in the quorum |
| Who reconciles logs | Leader reopens unresolved slots as needed | Leader overwrites divergence on the fly, while serving | A separate phase before serving begins |
| Rounds per write | 1 (Prepare is skipped while the leader is stable) | 1 (AppendEntries + ACK) | 1 (proposal + ACK), plus an explicit commit |
| Log ordering | Slots are independent, gaps possible | Strict prefix, no gaps | Strict prefix + primary order |
| Entries from a previous epoch | Reopened under a new number | Not committed by replica count — only indirectly, via committing an entry of the current term | Recovered or discarded during Synchronization |
| Membership changes | Not specified | Joint consensus or one-node-at-a-time | Dynamic reconfiguration (ZK 3.5+) |
| Main carriers | Spanner, Chubby, Ceph Monitors | etcd, Consul, CockroachDB, TiKV, KRaft | ZooKeeper only |
Applications of Paxos, Raft, and Zab in real-world systems
Below is where these protocols run in practice, organized by algorithm. The tasks themselves are almost always the same: cluster configuration storage, a coordinator with master election and locks, and data replication within the DBMS. The only difference is which protocol was available when the system was written.
Paxos in Google services and distributed databases
Paxos has become the foundation for a number of Google's internal systems. In particular, the globally distributed Google Spanner database uses Multi-Paxos for synchronous replication between data centers. Each data fragment (split) is stored with multiple replicas, which form a separate Paxos group with its own leader. If the leader fails, the group elects a new one, and the service remains available. However, external consistency (i.e., strict serializability with respect to the actual order of transactions globally) does not follow from Paxos alone. Paxos orders operations within a single replica group, while a transaction in Spanner can affect multiple groups—they are coordinated by a two-phase commit on top of Paxos groups. Ordering between transactions, which have no data overlap and are executed in different regions, is provided by TrueTime—a time API with clearly bounded error, built on atomic clocks and GPS receivers in data centers. TrueTime returns not a moment, but an [earliest, latest] interval, guaranteed to contain real time. This is the basis of the commit-wait technique: a transaction, having received a commit timestamp, waits until the uncertainty interval has elapsed and only then is it considered committed. This ensures that a transaction started after another transaction completes will receive a strictly higher timestamp. Without TrueTime, Spanner would be just Paxos replication, and its use as an example of global consistency would be meaningless.
Another well-known example is Chubby, Google's distributed locking service, which also implements consensus based on Paxos. Chubby stores small but critical configuration data (such as master node coordinates) and uses Paxos for high availability: even if nodes fail, consistent storage remains for clients. Paxos is also used for metadata replication in distributed file systems, though more often indirectly: GFS relied on Chubby, i.e., Paxos via an external locking service, rather than implementing it itself. HDFS took a different approach and uses its own quorum mechanism for the edit log—Quorum Journal Manager. While not technically Paxos, its recovery procedure is based on the same idea: a new writer first secures an epoch number from a quorum of JournalNodes and only then reconciles the history. The difference lies more in the scope of the task: QJM doesn't agree on arbitrary values, but on a sequence of log segments with a single active writer. Among file systems, Ceph uses Paxos directly — in its monitor service (Ceph Monitors), to agree on the cluster map.
This is a special case where consensus isn't the foundation of the system, but a one-time operation. Cassandra is built on eventual consistency and has no leader, but for conditional writes ("insert only if the key doesn't already exist") it requires true consensus: two clients mustn't simultaneously agree that the key doesn't exist. For each such operation, Lightweight Transactions performs a full Paxos round trip over the replicas of that key—four message rounds versus one for a regular write. The cost is so significant that LWT is used selectively rather than as the default mode. In 4.1, they attempted to mitigate this with a rewritten Paxos implementation (v2), but the nature of the overhead remained unchanged. A radical solution is Accord, a protocol without a dedicated leader that delivers a transaction in a single round when transactions don't conflict. It was included in the 6.0 branch, which currently (August 2026) is in alpha status, it is not in the stable 5.0 branch.
Cassandra shows a limit here: consensus does not have to be the architecture of the entire system, it can be a local tool for a single operation – and in this form its cost is most clearly visible.
Raft in orchestration systems, service discovery, and new DBMSs
Over the past ten years, Raft has displaced Paxos from almost all new open-source projects requiring consensus.
The most notable example is etcd, where Raft replicates the change log between nodes. The entire Kubernetes cluster state passes through etcd, so each container deployment is essentially a Raft commit. Consul uses Raft only for the portion of data that requires consistency: the service catalog, configuration keys, sessions, and locks. Everything else lives outside of consensus, a distinction we'll return to below.
In distributed DBMSs, Raft has become the basis for replication at the level of individual data ranges. This is because a single Raft group doesn't scale for writes: all commands pass through a single leader, and its disk and network interface card become the limiting factor for the entire cluster. The solution isn't just one Raft per system, but many: CockroachDB and YugabyteDB maintain a separate group for each range, with leaders of different groups residing on different nodes, and the load is spread across the cluster. Each group provides linearizability within its range and automatically switches leaders in the event of a node failure, transactions affecting multiple ranges are coordinated separately across groups. TiKV (the storage engine behind TiDB) is structured similarly, and its Raft implementation is extracted into a standalone Rust library, raft-rs, which is also reused by third-party projects.
Zab and ZooKeeper in coordination systems
Zab is used almost exclusively within ZooKeeper—it's a protocol written specifically for the product. ZooKeeper itself, however, has been the foundation of the Hadoop and Apache ecosystems for decades: distributed locks, master election, configuration nodes, and queues were built on it. For over a decade, it served as the coordinator for Apache Kafka: storing broker information, topic and partition configuration, ensuring cluster controller election, and ensuring that exactly one broker is the leader of a given partition. This dependency has now been eliminated. As part of KIP-500, Kafka received its own built-in consensus, KRaft, where dedicated controller nodes form a quorum and store metadata in the internal __cluster_metadata log. KRaft was declared production-ready in version 3.3 (2022), ZooKeeper mode was deprecated in 3.5, and 3.9 was the last version with its support. In Kafka 4.0, released on March 18, 2025, ZooKeeper support was completely removed, leaving KRaft as the only operating mode. A direct upgrade from a ZooKeeper-based cluster to 4.0 is not possible: an intermediate migration to KRaft in a 3.x version is required. However, a large number of 3.x installations still use ZooKeeper, so the Kafka + ZK combination will be around for a long time to come.
Another example is HDFS NameNode HA: ZooKeeper is used for automatic failover between Active and Standby NameNodes. This is accomplished through a separate ZKFailoverController (ZKFC) process next to each NameNode: it holds an ephemeral znode lock in ZK, and the disappearance of the failed node's session triggers failover. The metadata itself is not stored in ZooKeeper, the edit log is replicated via the Quorum Journal Manager, the same epoch mechanism discussed above. HA shouldn't be confused with HDFS Federation: the latter solves a completely different problem—horizontal scaling through multiple independent namespaces—and doesn't require ZooKeeper. In HBase (a NoSQL database on Hadoop), ZooKeeper stores information about the active region servers.
Where does the algorithm end?
Knowing Raft doesn't mean understanding etcd. The protocol defines how to maintain log consistency across nodes. Everything the system user sees—the data model, read guarantees, quorum loss behavior, and database growth limits—lies outside the protocol and is addressed by the implementation. Below are a few questions the protocol doesn't answer, and etcd, ZooKeeper, and Consul answer differently.
Who constitutes a quorum?
The protocol says "a majority of nodes," but doesn't specify which nodes actually count.
In etcd and ZooKeeper, all cluster members vote, and this limits cluster size: three or five nodes, going beyond that doesn't pay off. Consul is designed differently. A Raft quorum is formed by three to five servers, and each application machine runs a client agent that doesn't participate in consensus: it registers local services, performs health checks, caches responses, and proxies requests to servers. A cluster of three machines and a cluster of three thousand are the same Raft.
ZooKeeper arrived at a similar solution in a different way. Observers receive updates from the leader but don't vote, and they can be deployed in remote data centers—reads scale, and the quorum doesn't slow down.
Neither Raft nor Zab have either: they're layers on top of the protocol, and they determine the scale of the system more than the choice of protocol itself.
This also applies to the data model. etcd v3 stores a flat, sorted keyspace: the familiar /registry/pods/default/nginx hierarchy is the naming convention, and "get a subtree" is expressed as a range query by prefix. ZooKeeper retains a true znode tree with ephemeral and sequential nodes, and distributed locks, queues, and barriers are built on these primitives. Consul maintains a separate service catalog with its own schema on top of KV. Three data models are used on two algorithms because consensus agrees on the command log, and the commands in that log are of no concern to it.
What the reader sees
Neither Raft nor Zab offer linearizable reads for free: a quorum commit doesn't mean the write is visible on all nodes simultaneously. Who is responsible for freshness and when is a product-specific decision, and this is where the three systems diverge most significantly.
etcd delivers freshness by default. Regular reads go through leadership confirmation, and the client is guaranteed to see the result of the last successful write. For those who prioritize speed, there's a serializable mode: the response is returned by a local replica, which may be out of date.
ZooKeeper doesn't guarantee freshness by default. Reads are served by any server from its local replica, so a client can see a state that lags behind the last committed write. The only guarantee is that it won't see history backwards: the order of operations performed by a single client is preserved, and a revision once seen cannot be rolled back. This is sequential consistency, not linearizability. The difference is that linearizability requires not only the overall order of operations but also consistency with real time: a confirmed write must be seen by any subsequent read, regardless of which node it comes from. ZooKeeper provides the former and not the latter. To ensure a fresh read, the client calls sync before reading. ZooKeeper's ability to scale reads across all nodes relies precisely on this relaxation: nodes respond locally because they don't need to be fresh.
Consul devolves the choice to the individual request level: consistent goes through a quorum with confirmation of leadership, stale allows any server from its replica to respond, and the default mode is intermediate: the leader responds immediately based on its lease, so in theory it can return stale data if it has already been displaced but doesn't yet know it. Agent caching is also available, but it is enabled by an explicit flag and isn't enabled by default.
The practical consequence is simple: code that reads a key immediately after someone else's write and expects to see it works in etcd and silently breaks in ZooKeeper.
What happens when quorum is lost?
The protocol only says "progress stops." It doesn't describe what the system does in this case.
etcd rejects writes, and in linearizable mode, reads are also rejected, as the node can't confirm leadership and responds with an error. ZooKeeper stops writes but continues to serve reads from local replicas: they weren't fresh anyway, so degradation is gradual. Consul stops writing to the directory, but reads in stale mode continue to be served by servers, and agents continue to perform health checks locally. The results of these checks won't be written to the directory, and applications will receive an increasingly outdated picture.
The difference here is in the form of the rejection. In the first case, the application will receive an error and learn about the problem immediately. In the third, it will receive a plausible but outdated response and learn about the problem later, sometimes much later.
What happens to the log in production?
Raft describes the mechanics of log compaction, but not the policy: when to take a snapshot, what to do with old data, where growth limits lie. This is left to the implementation, and this is where production most often breaks.
MVCC, which gives etcd a revision history and the ability to subscribe to changes from a given point, comes with its main gotcha: old revisions are not deleted automatically. They are removed by compaction, and the freed space is returned to the file system only by defragmentation—a separate operation that locks the node for the duration. Without both, the database grows, and when --quota-backend-bytes (2 GB by default) is reached, the cluster goes read-only with a NOSPACE alarm. For Kubernetes, this means the cluster continues to operate but stops accepting any changes—a state that must be exited manually.
The second source of growth in etcd is watch subscriptions: each controller monitoring keys maintains a thread, and in large clusters, there are thousands of them.
ZooKeeper writes snapshots and the transaction log to disk, but doesn't delete old files. This is controlled either by autopurge in the configuration or by the administrator. A forgotten setting is a common cause of disk filling on a ZK node.
What you'll have to configure manually
Not a single article about Raft specifies the proper election timeout. Too short, and the cluster re-elects the leader at every spike in network latency, too long, and downtime during a real failure extends to seconds. The starting point is usually an order of magnitude higher than the typical RTT between nodes, and then it's adjusted based on metrics.
Second, disk. Commit in Raft is limited by the leader's fsync, so SSD is essential: network storage with unpredictable latency turns the cluster into a generator of false re-elections.
Third, monitoring. A cluster of three nodes, where one has been down for a long time, appears healthy: there's a quorum, writes are going through. But there's no more headroom, and the next failure will stop writes. You need to monitor the number of alive nodes and the commit latency—the fact that "is it responding or not" says nothing about the safety margin.
What no one else has
None of the three algorithms are designed for a quorum that spans across regions: each write requires a network round-trip to reach a majority, and interregional latency translates directly into commit latency.
Therefore, etcd has no built-in geo-replication—the cluster is kept within a single data center or nearby zones. Consul for multi-DC sets up independent Raft quorums in each data center and loosely links them by exchanging service registrations, without global consensus. Global consistency in systems that require it is built on top of, rather than through, consensus: in Spanner, through TrueTime and a two-phase commit between Paxos groups, in Cosmos DB, through a separate interregional replication mechanism with a selectable consistency level.
When consensus isn't needed
Before setting up a cluster, it's worth checking whether it's needed at all.
Eureka, the Netflix service registry, operates without consensus at all: each node accepts records independently and replicates them to the other nodes for best-effort. When a network partition occurs, nodes on either side diverge but continue to respond. For a registry where a client still rechecks the instance's availability when accessing it, this is a reasonable tradeoff—an outdated list of addresses is more useful than an unavailable registry.
The same technique is used within Consul. Cluster membership and failure detection are based on the Serf gossip protocol, where a few seconds of desynchronization is acceptable and cheaper than quorum, while the service catalog is written using Raft. The line is drawn where divergence ceases to be harmless: a node's life can be detected with a delay, but lock ownership cannot.
Consensus is expensive, and mature systems use it selectively.
Conclusion
The practical choice today seems simple. For new code, choose Raft: there are more implementations, the ecosystem is more vibrant, and its clarity really pays off during debugging. ZooKeeper is used in two situations: you're part of a Hadoop ecosystem or serving those same Kafka 3.x installations discussed above, or you need its primitives on a znode tree: ephemeral nodes and watches provide locks and queues for next to nothing, but building them on top of a KV storage system is significantly more expensive. Paxos is rarely used in new open source projects. It lives inside large systems that were written before Raft and have since inherited it—Spanner, Chubby, Ceph. It's always a custom implementation within the product, not a ready-made component that can be plugged in.
But before choosing, it's worth asking the question up front: is consensus even necessary? It buys consistency at the cost of delays for each write and stalls when quorum is lost. If a discrepancy of a few seconds is harmless, gossip is cheaper. If operations are commutative, CRDTs can handle it without coordination. If the load fits on a single node, a replica with manual failover is more reliable than a three-machine cluster that no one knows how to fix.
Where consensus is truly needed, it's increasingly hidden inside something else: Kubernetes carries etcd, Kafka carries KRaft, CockroachDB carries a Raft group for each data range. Understanding how this works is essential for debugging: to understand why the cluster crashed and what went wrong.
Top comments (0)