Why Meerkat did not use Raft, Paxos or Viewstamped Replication
Cloudflare's Meerkat is an experimental distributed consensus service that manages the company's internal global control plane. It runs on QuePaxa, a consensus algorithm published by Tennage & Băsescu et al. in 2023. Choosing it was unusual: most consensus systems rely on well-established algorithms such as Raft, (Multi-)Paxos or Viewstamped Replication, which are well understood, mature and generally work well.
The catch is where Meerkat runs. The common algorithms depend on a single leader process that must stay available and exhibit predictable latency. If the leader fails, slows down or is cut off, the whole system stalls until a replacement is elected — unacceptable for Meerkat's environment. QuePaxa promises better stability under volatility, largely because it does not need a leader to make progress.
Meerkat's constraints
Meerkat is a replicated system in which replicas agree on an ordered log of events, each decided by consensus. The core guarantee — replicas never decide conflicting values — keeps those logs from diverging. Applications such as a key-value store are built on top: each log entry is a get or a put, and because the logs match, every replica constructs the same KV state. Consul, etcd and Apache ZooKeeper are comparable systems.
What sets Meerkat apart is global scale. Its cluster may span continents over links with high and variable latency — an unusual setting, since consensus systems are typically deployed in smaller, more local networks with strict latency requirements.
Where consensus breaks down at global scale
All consensus algorithms agree on the same value, but many become disproportionately slow or unavailable when the network degrades even though no machine has crashed. Cloudflare has seen this: in 2020, a partially failed core network switch slowed a consensus-powered system so that the dashboard ran 80x slower than usual for six hours. No data was lost, but writes were unavailable until the problem was fixed.
Two recurring traits drive this degradation: destructive interference and fault detection. QuePaxa avoids both.
Destructive interference in Paxos
Paxos has two process types, proposers and acceptors, and two phases. In Prepare, a proposer sends a ballot number to a majority of acceptors; that number is a promise that they will only accept proposals at that ballot or higher. In Accept, the proposer sends its proposal with the ballot number to a majority again, and if a majority still holds that ballot, the proposal is accepted and can be safely decided.

Trouble starts when proposals overlap: another proposer can interleave a higher ballot between the two phases and block lower ones. Two proposers can keep blocking each other — destructive interference — and it worsens as more proposers join. Even with no crashed replicas, multiple proposers plus a misbehaving network can block Paxos. Formally, it does not guarantee liveness without partial synchrony, the assumption that all messages eventually arrive within a bounded time.
The leader trade-off
To prevent constant competition, Raft, Multi-Paxos and Viewstamped Replication designate a leader proposer as the only replica allowed to make proposals. This orders concurrent requests, avoids competing proposals, and cuts decisions to a single network round-trip instead of two. While the leader is healthy and the network behaves, leader-based protocols are fast.

The cost is that the leader must remain operational and reachable. If it fails, slows or is disconnected, the system stalls until the remaining replicas detect the failure and elect a new leader.
Recovery reinvites interference
Raft picks a new leader by majority vote. A replica that suspects the leader has failed announces itself as a candidate and requests votes; more than half in favor makes it leader, otherwise a new election is called. Several replicas can become candidates at once simply by detecting the failure, and their simultaneous bids recreate Paxos-style interference — two candidates can each deny the other a majority, and the more elections fail, the more replicas try.

The result can be a metastable failure: a pattern that sustains itself after the original cause is gone. A two-second outage or a momentarily faulty switch can make the leader appear dead, force an election that fails, and trigger further elections long after the network has recovered. Ideally, consensus would need no recovery process at all, since recovery is complicated, interference-prone and a source of downtime in its own right.
Fault detection cannot be certain
Leader election also depends on detecting failure, and no process can directly observe that a remote one has died — only that an expected message has or has not arrived. Detectors therefore rely on patterns such as heartbeats or acknowledgements and guess when the expected timing slips.
In asynchronous networks there is no guaranteed upper bound on message delivery. Most messages arrive on time, but bursts of latency or lost connectivity can stretch traversal time without warning. A server that stays silent may have failed or may simply be behind a slow network; over the wire the two are indistinguishable. Any practical detector has to guess, and sometimes the guess is wrong.

In leader-based systems that wrong guess starts an election and halts the system until a new leader is in place. Fault detection is fundamentally error-prone in asynchronous networks, and each detection error becomes downtime.
Even accurate detection is slow
Correct detection carries its own cost: detector response time must scale with network latency, because timeouts cannot sit below it. Raft is commonly deployed with an election timeout of five to ten times the network round-trip time — high enough to avoid false elections. Since elections halt the system, timeouts are set conservatively. A round trip halfway around the world takes hundreds of milliseconds, so with a timeout of several round trips, noticing a failed coordinator can take around a second — slowest in exactly the high-latency global networks where it matters most, and the system is down until the detector reacts.
Why an asynchronous protocol fits
Any consensus algorithm built on a strict leader or on accurate timeouts will eventually stall in a system that runs over the Internet. That drove the search toward protocols designed for asynchronous environments — ones that do not depend on a well-behaved network or precise timing. The result was QuePaxa, published in 2023 by Tennage & Băsescu et al.
QuePaxa can reach consensus in a single round trip when conditions are favorable, yet degrades gracefully during latency spikes, connectivity problems and server failures. It gets there through three design choices: an optional leader, no reliance on fault detection, and constructive interference between proposers.
As in Paxos, there are two roles. Proposers submit proposals to be decided, and recorders act as intermediaries, recording every proposal they see.

Cooperation instead of competition
Rather than competing to get their own proposals decided, proposers in QuePaxa work cooperatively toward a proposal everyone supports. Each proposal carries a priority in the form of a random number, and the optional leader holds an exclusive maximum priority. Proposers send proposals to recorders, which propagate them to other active proposers. A proposer that receives a higher-priority proposal than its own adopts it and begins broadcasting that proposal instead. Collectively, proposers converge on the highest-priority proposal they know, so no proposer can lock another out of deciding indefinitely.

Spreading proposals well enough to agree is not guaranteed, so proposers retry; each attempt is a round. The more proposers submitting proposals, the more likely they are to converge on the highest-priority one. This is what makes QuePaxa randomized: random priorities are likely, but not guaranteed, to produce consensus on the highest known priority within a round, yet agreement is guaranteed given enough rounds.
One proposer is designated leader and is the only one able to decide in a single round trip. It always proposes with the highest priority; if it knows its proposal reached a majority of recorders before any other proposer, it decides immediately. Clients need not send requests to the leader — any proposer can propose, and if the leader goes down, clients keep using the others. The leader is completely optional; it is simply more likely to decide, and to decide faster.
Hedging and the hedge timeout
Because only the leader has the single-round-trip path, it should be used whenever possible. To exploit this fast path without creating a single point of failure, clients hedge: they send proposals to every replica, and non-leader replicas wait a short timeout so the leader can decide on its own. In the implementation, clients wait the hedge timeout instead of replicas, which cuts network messages while producing the same result.
The hedge timeout differs fundamentally from the timeouts in Raft or Multi-Paxos. It is not fault detection, so it is not constrained by network latency; it is locally determined by replicas and can be as small as they like. A five-millisecond timeout in Raft on a network with 100-millisecond latency would freeze the system, whereas a five-millisecond hedge timeout in QuePaxa merely increases the number of active proposers.
Hedging is not free: more proposers means more proposals broadcast and a greater chance a round fails to decide. It is a tradeoff — a lower hedge timeout reacts faster to leader changes at the cost of extra bandwidth and possibly longer time to decide.
If the leader dies, recovery speed is not bound by network latency. Since anyone can propose, QuePaxa handles leader failures proactively through hedging rather than reacting to them, which is how it avoids fault detection altogether.
The four phases
A QuePaxa round consists of four phases; if no decision is reached in the last one, a new round begins. At the start of each phase, proposers broadcast their currently adopted proposal to all recorders and advance once a majority replies.
- Phase 0 (Propose and Adopt): Proposers pick a random priority, send proposals to recorders, and adopt the highest-priority proposal received from a majority. On the first round, if the leader knows its proposal reached a majority first, it decides immediately.
- Phase 1 (Spread): Proposers spread their adopted proposal to a majority of recorders.
- Phase 2 (Check and Decide): Proposers ask a majority of recorders for the highest-priority proposal seen in the previous phase; if it matches their own, they decide.
- Phase 3 (Carry Forward): Any proposer that did not decide adopts the best proposal it sees from a majority of recorders, preparing for the next round.

Fast path and majority intersection
Phase 0 does three things: it randomizes priorities, which it must do to circumvent the FLP impossibility theorem; it checks whether the leader reached a majority first; and it helps proposers converge if the leader did not. The leader's proposal is not randomized and always carries the highest possible priority.

When the leader's proposal reaches a majority of recorders before any other, and replies confirm it, the leader decides immediately. This is safe by majority intersection: any two majorities of recorders share at least one recorder. Any other proposer querying a majority will therefore encounter the leader's proposal, and because that proposal has the highest priority, it will adopt it. No other proposal can be decided.

Contested rounds
With concurrent proposers, the leader may fail to reach a majority first or receive a reply supporting another proposer, and the fast path is blocked. Proposers then adopt the highest-priority proposal from a majority and move on. In the example below, convergence is artificially prevented by delaying the leader's messages.

In Phase 1, proposers spread what they adopted in Phase 0, and recorders track the highest-priority proposal they observe — a simple but critical step that prevents later deciding on a lower-priority proposal. Majority intersection again applies: any majority queried in the next phase includes at least one recorder that saw the adopted proposal. Here, the leader's message to the third recorder is delayed, so that recorder does not adopt it.

Phase 2 is where a decision can happen. Each proposer asks a majority of recorders for the highest-priority proposal observed during Phase 1. If the highest returned is still its adopted proposal, it decides. The leader sees its own proposal from a majority and decides safely; the other proposer gets conflicting summaries and cannot decide. As in Phase 1, recorders keep track of the highest-priority proposal received.

In Phase 3, a proposer that did not decide spreads its proposal again and adopts the best found among a majority of recorders. The remaining proposer discovers the decided proposal and carries it forward. This is deliberate: if a decision occurred in the previous phase, a majority of recorders holds that proposal, and remaining proposers are guaranteed to adopt it.

After the fourth phase, a new round starts; the leader fast path is gone, and deciding requires convergence in Phase 2. Proposal adoption makes decisions exponentially easier as rounds progress. The paper predicts a 50% chance of deciding per round, though in practice it is much higher thanks to convergence.
Taken together, Phase 0 supplies the one-round-trip fast path. If it fails, random priorities and adoption help proposers converge instead of compete, majority intersection makes deciding in later phases safe, and Phase 3 carries what was learned into the next round. No proposer must detect a failed leader before making progress, and a failed round does not discard work already done.
What this buys Meerkat
In evaluations with servers spanning nearly all continents, Meerkat has kept processing requests while the leader crashed, disconnected or slowed, and has never been seen to stall completely.

Throughput has been generally predictable. Upwards of 95% of decisions are made by the leader in the first phase. When a decision is not reached there, throughput drops momentarily to at most a third of the usual rate, indicating that three round trips — three phases — were needed instead of one. The system slows but does not halt.
QuePaxa also makes it safe to switch which replica acts as leader while the cluster runs. Since the leader is not the exclusive driver of decisions and proposers cooperate, a temporarily suboptimal leader is far less limiting than in algorithms where a leader misconfiguration could stall the system completely, so the active proposer can be tuned dynamically with little risk to cluster stability.
Why QuePaxa for a global deployment
Meerkat's global-network requirements meant the team could not simply default to the well-known consensus protocols. Those defaults did not match the constraints. Turning to decades of published research from academia and industry led instead to QuePaxa.
Adopting QuePaxa means taking a less-traveled path. It lacks the extensive battle-testing that Raft or Paxos have received, and the work goes further than the paper: the original crash-stop design is being extended to support crash recovery. That extension raises the bar, requiring careful engineering and stronger correctness evidence than typical systems demand.
Verification and testing strategy
To meet that bar, the QuePaxa implementation — and Meerkat as a whole — is being formally verified. This work runs alongside extensive simulation and fault-injection testing.
- Formal verification of Meerkat and of QuePaxa's Rust implementation
- Simulation testing
- Fault-injection testing covering failures that are difficult to reproduce in production
What follows
Later posts in the series will cover the verification approach for Meerkat and for QuePaxa's Rust implementation, the failure testing, benchmarks, and lessons learned from turning an academic protocol into a production system. Further Meerkat updates will appear on the Cloudflare Blog, and more on Cloudflare's research work is available at Cloudflare Research.



