QuePaxa Lets a Global Control Plane Keep Deciding While Links Stall

TL;DR

• QuePaxa is a consensus algorithm published in 2023 by Tennage, Băsescu and co-authors that lets a group of machines agree on an ordered log while any proposer can move the protocol forward.
• Cloudflare says it is building Meerkat, an experimental consensus service for its internal global control plane, on QuePaxa, in a post published on 11 November 2026.
• Leader-based algorithms such as Raft, Multi-Paxos and Viewstamped Replication recover by detecting a failed leader and electing a replacement, and that recovery path is where a wide-area network hurts most.
• QuePaxa keeps proposers cooperating: priorities are random, a proposer adopts any higher-priority proposal it meets, and clients hedge by sending a request to every replica.
• A round has four phases (propose and adopt, spread, check and decide, carry forward), and a proposer that misses the one-round-trip fast path carries its work into the next round.
• In Cloudflare's own Meerkat tests the decision rate fell to about 65% of its usual level while a failed leader was being replaced and returned to 100% a minute later; Cloudflare describes QuePaxa as less battle-tested than Raft and is formally verifying its implementation, so the open question is the evidence a buyer can inspect.

Every control plane eventually meets the same question: what happens to the shared record when the network between its replicas turns bad? Cloudflare answered it in public on 11 November 2026, when engineers João Pedro Leite, Bob Halley and James Larisch explained why the company's experimental consensus service, Meerkat, runs on QuePaxa, a protocol published in 2023.

The post is unusually specific for a vendor blog. It names the alternative algorithms, explains the failure mode that pushed the company away from them, walks through all four phases of a QuePaxa round, and reports what happened to Meerkat's decision rate when a leader was taken out of service. That combination makes it useful reading for anyone running a self-hosted control plane, a database with a replication layer, or a queue that has to keep ordering events across regions.

What QuePaxa is and where Cloudflare runs it

QuePaxa is a consensus algorithm, which means it lets a set of replicas agree on one ordered sequence of values even when some of them crash or lose contact. Meerkat uses that sequence as a log: each entry is a get or a put, so every replica that applies the same log arrives at the same key-value state. Cloudflare compares the shape to Consul, etcd and Apache ZooKeeper, and describes Meerkat as an experimental service still in development.

The difference from those systems sits in the deployment geography. A Meerkat cluster can span continents, which puts links with high and variable latency inside the protocol's working assumptions. Cloudflare writes that consensus systems usually run in smaller, more local networks with strict latency requirements, and that Meerkat was designed for global scale from the start.

Why leader-based consensus stalls on a global control plane

Paxos, the ancestor of most of these protocols, has proposers and acceptors and two phases: prepare and accept. Any proposer may start a ballot, and a second proposer can interleave a higher ballot between the two phases, which blocks the first one. When two proposers repeat that against each other, Cloudflare calls the result destructive interference, and the protocol stops deciding even though every machine is healthy.

Raft, Multi-Paxos and Viewstamped Replication answer that with a leader that holds the only right to propose. While the leader is reachable, a decision costs a single network round trip. When the leader fails, slows down or loses its connection, the remaining replicas have to notice and elect a replacement, which is where the design pays its price.

Cloudflare gives two reasons the price is high on a wide-area network. The first is that detection depends on expectations: a replica can only observe that an expected message has not arrived, so any practical detector guesses, and a wrong guess starts an election that halts decisions. Raft is commonly deployed with an election timeout five to ten times the network round trip, so detection on an intercontinental link is slow by construction.

The second is that elections inherit the interference problem. Several candidates can become candidates at once and block each other from a majority, and the pattern can outlast the fault that started it. Cloudflare calls that a metastable failure: a two-second outage, or one misbehaving switch, can trigger elections that keep running after the network is healthy again.

How QuePaxa keeps proposers cooperating

QuePaxa keeps the two Paxos roles and renames the second one. Proposers submit values; recorders act as intermediaries and record every proposal they see. Each proposal carries a random priority, and a proposer that meets a higher-priority proposal adopts it and starts broadcasting it in turn.

That single rule changes the incentive inside the protocol. In QuePaxa, a proposer adopts the highest priority it can find because that is the value most likely to be decided this round. Cloudflare describes the outcome as constructive interference, and notes that the protocol stays randomised on purpose: priorities are drawn at random to get around the FLP impossibility result, which rules out a deterministic protocol that always decides in an asynchronous network.

One proposer holds the maximum priority and is the only one able to decide in a single round trip. Clients do not have to send requests to it. In the paper, clients hedge by sending to every replica, and the non-leaders wait a short timeout so the leader can finish first. Cloudflare implements this timeout at the client: clients wait for it, which reduces the number of messages sent over the network, and a short timeout only creates more active proposers.

What the four phases do in each round

A round runs through four phases, and each phase advances when a proposer hears back from a majority of recorders. In phase 0, propose and adopt, proposers draw a priority and send their proposal, then adopt the highest priority they see from a majority. If, in the first round, the leader learns its proposal reached a majority first, it decides immediately.

Phase 1 spreads the adopted proposal to a majority of recorders, which keep the highest priority they observe. Phase 2 asks a majority what the highest priority was in the previous phase: a proposer whose own proposal still wins decides, and one that sees something higher does not. Phase 3 carries the best proposal a proposer can find into the next round, so a failed round keeps its progress.

Safety rests on majority intersection, the property that any two majorities of recorders share at least one member. Cloudflare's argument for the first round is compact: the leader reached a majority in phase 0, so any other proposer querying a majority in phase 2 meets that proposal and adopts it, and because the leader's priority is the maximum, no lower value can be decided.

What Cloudflare measured in Meerkat

Cloudflare reports results from Meerkat clusters with servers on nearly every continent. The claim it makes first is availability: Meerkat kept processing requests while a leader crashed, disconnected or slowed down, and the company says it has never seen the system stall completely.

The post includes the measurement behind that claim. When a leader failed, QuePaxa fell back to decisions in phase 2 and the decision rate dropped to around 65% of its original level, then returned to 100% when the faulty leader was replaced, a minute after the failure. Cloudflare also reports that upwards of 95% of decisions are taken by the leader in the first phase, which keeps throughput stable, and that the slower path costs at most a third of the usual rate because it needs three round trips.

Those figures come from one operator's implementation, and the same post lists what makes them worth reading carefully. The comparison between in-cluster tests and a hostile network is still missing: Cloudflare promises later posts on its Rust implementation, its fault-injection testing and benchmarks, and says nothing yet about the throughput cost of hedging when many proposers are active at once.

What the choice leaves open

Cloudflare states the limits of its own decision. QuePaxa "has not been battle-tested as extensively as Raft or Paxos", and the company is extending the original crash-stop design to handle crash recovery, which it calls work that demands stronger evidence of correctness than usual systems. It is formally verifying the implementation and running simulations alongside, and none of that evidence has been published yet.

For a team that operates a replicated service, the useful part of the post is the diagnostic pattern. Ask which failure the protocol recovers from, and how long recovery takes once a link between replicas degrades. An election timeout expressed as a multiple of the round trip is an admission that latency enters the recovery path. A client-side hedge timeout, as Cloudflare implements it, is a different arrangement, and it moves the cost of a failure from unavailable time to extra messages.

The same reasoning applies to the components a small company runs today: etcd behind Kubernetes, a replicated Postgres cluster, a self-hosted queue. None of them is about to switch protocol, and the question worth asking is narrower: what does the operator notice when the link between replicas degrades, and which metric carries that signal? Designing alerts that explain an incident applies the same diagnostic discipline after the fact.

Sources

Source: Choosing QuePaxa, an unusual consensus algorithm — Cloudflare Blog, 11 November 2026, blog.cloudflare.com/choosing-quepaxa, retrieved 2026-11-12 (Meerkat is an experimental distributed consensus service for Cloudflare's internal global control plane; QuePaxa was published in 2023 by Tennage and Băsescu et al.; Paxos uses proposers and acceptors in prepare and accept phases; destructive interference blocks a proposal when a higher ballot interleaves between the phases; Raft, Multi-Paxos and Viewstamped Replication add a leader that holds the only right to propose; a Raft election timeout is commonly five to ten times the network round trip; a metastable failure continues after its cause is removed; QuePaxa has proposers and recorders, random priorities, an optional leader holding the maximum priority and a hedge timeout that is not fault detection; four phases per round named propose and adopt, spread, check and decide, carry forward; safety rests on majority intersection; in 2020 a partial failure of a core Cloudflare network switch left the dashboard operating 80 times slower than usual for six hours with no data loss; in Meerkat, upwards of 95% of decisions are taken by the leader in the first phase, the decision rate fell to around 65% of its original level during a leader failure and returned to 100% when the leader was replaced a minute later, and the slower path costs at most a third of the usual rate; QuePaxa has not been battle-tested as extensively as Raft or Paxos and Cloudflare is extending the crash-stop design to crash recovery while formally verifying the implementation).

Source: Meerkat — Cloudflare Blog, blog.cloudflare.com/meerkat-introduction, retrieved 2026-11-12 (Cloudflare's announcement of Meerkat, an experimental distributed consensus service designed to manage the company's internal global control plane, described as comparable in shape to Consul, etcd and Apache ZooKeeper).

Source: Cloudflare's QuePaxa post of 11 November 2026 and its Meerkat introduction, both retrieved 2026-11-12. Every phase name, measurement, timeout rule and figure above traces to those pages; the readings of what an operator should ask about recovery are Netics analysis. Images: four figures from the Cloudflare post and one capture of it, reproduced with credit, plus three Netics editorial diagrams. Netics editorial, neticslabs.com.