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.

In the Prepare phase, a proposer sends a ballot numbered “1” to three acceptors. The three acceptors reply. Then, in the Accept phase, the proposer broadcasts its proposal to the three acceptors. The acceptors have not received any other ballot, and so they accept the proposal. They reply to the proposer with this information, and the proposer decides.

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.

There is a single leader replica, wearing a crown, that is the only one allowed to send proposals to other servers, called “replicas”. All they do is accept the leader’s proposal.

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.

There is a greyed out leader that has crashed, and four other replicas. Two replicas are candidates for leadership, and are trying to acquire a majority of votes to become leader. They both need three votes, but they each have only acquired two votes (their own and another replica’s). No candidate is elected.

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.

A user is waiting for a response from a server. The response is taking a while. The user questions whether the network is slow, or if the server crashed.

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.

Two proposers, one blue and the other red, are opposite each other, separated by three servers labeled “Recorder”. Each proposer sends messages to each recorder.

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.

Two proposers, one blue and the other red, are opposite each other, separated by a single recorder. The blue recorder proposes a proposal with priority “2”. The recorder records the blue proposal and replies to the blue recorder, with the same blue proposal. Then, the red proposer sends a proposal with priority “1” to the recorder. The recorder replies to the red proposer with the higher priority blue proposal. The red proposer, upon receiving the reply adopts the blue proposal with priority “2” as its new proposal.

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.
A flowchart shows how QuePaxa’s phases progress. The flowchart is vertically aligned. There are four major steps in the flowchart, each one representing a phase in the QuePaxa protocol. The flowchart starts with a block titled “Phase 0 (Propose & Adopt)”, which has two arrows: one to the right, pointing at block labelled “Decide”, via an arrow labelled “Leader Fast Path”, and another arrow labelled “Majority Replies” pointing down at a block titled “Phase 1 (Spread)”. The Phase 1 block has a single arrow labelled “Majority Replies”  pointing below to the next phase block “Phase 2 (Check & Decide)”. The Phase 2 block has an arrow labelled “Proposal has Max Priority” pointing to the right, to a block titled “Decide”, and another arrow labelled “Majority Replies” pointing down to the final Phase block: “Phase 3 (Carry Forward)”. The Phase 3 block has a single arrow labelled “New Round” pointing back up to the Phase 0 block.
Flowchart of QuePaxa’s phase and round progression.

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.

The image shows a message passing diagram, where time progresses from left to right. There are five lanes. At the leftmost side of the diagram, there are, ordered vertically: a blue server with a crown, labelled “Leader”, with a blue ribbon attached to it, and an infinity sign at the center of the ribbon; three violet servers with a pen and paper, each labelled “Recorder”; a red server (with no crown), with a red ribbon attached to it, and a 1 at the center of the ribbon. The blue leader and the red proposer both broadcast their current proposal to every recorder. The recorders record and reply with the first proposal they receive. The leader reaches the first and second recorder first, while the red proposer reaches the third recorder first. The leader receives a majority (2) of replies each carrying the leader’s proposal. The leader sees that all proposals in the majority are its own and decides. The red proposer receives a majority (2) of the recorder’s replies, from the second and third recorders, who replied with the leader’s proposal and the red proposer’s proposal, respectively. The red proposer adopts the leader’s proposal, since it is the one with maximum priority in the majority it received.

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.

Diagram with three recorders. Two of them have recorded the leader’s proposal, while the other has recorded the red proposer’s proposal. The diagram shows how any groupings of two recorders must share one recorder by adding a semi-transparent Venn diagram on top of the recorders.

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.

The blue leader proposer and the red proposer both broadcast their current proposal to every recorder. The recorders record and reply with the first proposal they receive. The leader reaches the first recorder first, while the red proposer reaches the second and third recorders first. The leader receives a majority (2) of replies, containing its own maximum priority proposal and the red proposer’s proposal with priority 1. The leader adopts the proposal with the greatest priority which is its own. The red proposer receives a majority (2) of the recorder’s replies, from the second and third recorders, both containing the red proposer’s proposal. The red proposer adopts its own proposal, since it is the one with maximum priority in the majority it received. The reply from the third recorder arrives late, not in the majority, so it isn’t considered for adoption.

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.

The blue leader proposer and the red proposer both broadcast their current proposal to every recorder. The leader’s message to the third recorder is lost and never reaches the recorder. The first and second recorder each receive the leader’s proposal, with maximum priority, and the red proposer’s proposal, with priority 1. The third recorder only receives the red proposer’s proposal. Each recorder records the proposal with highest priority for the next phase. The first and second recorder record the leader’s proposal, while the third recorder records the red proposer’s proposal.

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.

The blue leader and the red proposer both broadcast their current proposal to every recorder. The first two recorders recorded the leader’s proposal with maximum priority in the previous phase, while the third and final recorder recorded the red proposer’s proposal, with priority 1. Each recorder replies to the proposers with the proposal that the recorder has adopted. The leader receives a majority (2) of replies from the recorders, each carrying its proposal. Of that majority, the proposal with the maximum priority is its own, so it decides it. The red proposer receives a majority (2) of replies from the recorders, one carrying the red proposer’s proposal, and another carrying the leader’s proposal. Of those two, the proposer's own proposal does not have the greater priority, so the red proposer cannot decide, and progresses to the next phase.

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.

The red proposer fetches the recorded proposals at each recorder, all of which are the leader proposal with maximum priority. When the proposer receives a majority (2) of the replies, it adopts the proposal with the maximum value, which is the leader’s proposal.

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.

Two graphs, labelled “RELATIVE DECISION RATE” and “SHARE OF DECISIONS BY PHASE”, both ranging from 0% to 100% on the y-axis, and from 14:58 to 15:09 UTC on the x-axis. The decision-share graph is split among two phases: Phase 0 (1 round trip) and Phase 2 (3 round trips). A red arrow points to a vertical dashed line, aligned at 15:00:32, labelled “leader failure”, and another arrow points to another vertical dashed line at 15:01:25, labelled “leader replaced”. Between those two dashed lines, the relative decision rate falls from 100% to around 65%. During that same time, the share of decisions changes first, from 100% in Phase 0 to around 95%, then drastically falls to 0%, with 100% of decisions happening in Phase 2. After the leader is replaced at 15:01:25, the decision rate climbs back up to 100%, and the decision rate similarly recovers to 100% in Phase 0.
QuePaxa falling back to Phase 2 decisions due to a leader failure. The decision rate decreases to around 65% of its original rate, and returns to 100% when the faulty leader is replaced, a minute after failing. At no point did the system halt.

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.