Cloudflare's QuePaxa Keeps Deciding at 65% Speed With a Dead Leader
On November 11, 2026, Cloudflare published the first post in a series on Meerkat, an experimental consensus service that manages the company's internal global control plane. The service is not the story. The algorithm inside it is. Meerkat runs QuePaxa, a consensus protocol published in 2023 by Tennage, Băsescu and colleagues that had never been deployed in production anywhere before Cloudflare picked it. The rest of the industry runs Raft or Paxos. Cloudflare evaluated those, hit a wall, and went shopping in the research literature instead.
The wall was the network itself.
Why leader-based consensus falls apart on the internet
Raft, Multi-Paxos and Viewstamped Replication share a skeleton. One leader drives everything: clients send it commands, it replicates entries to a quorum of followers, it commits. The design assumes the leader is reachable and that its latency is roughly predictable. Inside one datacenter, or across a few zones of one region, that assumption is free. Round trips are sub-millisecond and steady, and the leader rarely disappears.
Meerkat runs across continents over the public internet, where Cloudflare describes the links as carrying high and variable latency. Two properties of leader-based protocols turn that environment into a stalling system.
The first is fault detection by timeout. A follower decides the leader is dead when no heartbeat arrives inside some window. On a local network that window can be tiny and still be safe. Over the internet, latency spikes are routine, so the window has to be generous, and a genuinely dead leader goes unnoticed for seconds. Worse, a leader that is merely slow rather than dead can trigger an election that replaces a working leader with a worse one.
The second is destructive interference. When proposals, retries and elections collide, they waste rounds. Timeouts cancel in-flight decisions and the protocol spends capacity undoing its own work. Cloudflare's post is blunt about the consequence: common consensus algorithms suffer in wide-area networks with volatile connectivity and latency, because everything depends on one leader being available with predictable latency. If the leader goes down, or just gets slower, the whole system slows with it until a replacement is elected.
What QuePaxa changes
QuePaxa keeps the Paxos cast of characters but rewrites the script. Proposers submit values to be decided. Recorders act as intermediaries and record every proposal they see. The differences are three design choices.
The leader is optional. QuePaxa can run with a leader, and that leader holds an exclusive maximum priority so its proposals usually win. But if it vanishes, nothing breaks. The remaining proposers keep working without an election, because progress was never defined as "the leader is alive."
Every proposal carries a random priority, and proposers cooperate. Instead of competing to get their own values decided, they converge on the highest-priority proposal on the table. Recorders propagate each proposal to all active proposers, and each proposer keeps a queue of proposals to decide in order, which is the Que in QuePaxa. A message from another proposer is not an obstacle; it is information that also moves your own pending proposals forward. Cloudflare calls this constructive interference, a deliberate inversion of the collision behavior in leader-based protocols.
No fault detection at all. There is no timeout that declares a peer dead. Slow responders are simply slow, and decisions form from whichever responses arrive. That is the honest stance for a network where the difference between "dead" and "having a bad minute" is genuinely unknowable from the message stream alone.
The payoff: under favorable conditions QuePaxa decides in a single round trip, and under latency spikes, connectivity loss or server failures the decision rate degrades instead of the system halting.
The number worth remembering
The fault-injection result is the most concrete thing in the post. Kill the leader and QuePaxa's decision rate drops to roughly 65% of normal as it falls back to a slower decision phase. It never halts at any point. Replace the faulty leader, about a minute later in their test, and the rate returns to 100%. Compare that with the leader-based behavior the post describes: leader down means the system slows or becomes unavailable until a replacement takes over. Same failure, degraded service versus stalled service.
| Raft / Multi-Paxos | QuePaxa (Meerkat) | |
|---|---|---|
| Leader | Required for progress | Optional, max priority only |
| Failure detection | Timeouts and elections | None, decisions form from arrivals |
| Concurrent proposals | Destructive interference | Constructive, queues share information |
| Leader failure | Stalls until replaced | ~65% decision rate, never halts |
| Comfort zone | One region, a few zones | Continents over the public internet |
What an unproven algorithm costs
Cloudflare is not pretending this is a free trade. The original QuePaxa paper assumes crash-stop failures, where a crashed node stays crashed. Real servers reboot and rejoin holding stale state, so Cloudflare is extending the algorithm to crash recovery, which is exactly where consensus bugs historically hide. Their answer is formal verification of the Rust implementation plus simulation and fault-injection testing, and the post says plainly that this demands careful engineering and stronger evidence of correctness than usual systems. Follow-up posts on verification and benchmarks are promised. Until those land, Meerkat is a bet being underwritten with verification money, not a finished product. It is labeled experimental and there is no public path to adopting it.
Should you care?
Probably not directly. If your consensus group lives in one region, Raft remains the right call. The implementations are mature, the semantics are understood, and your network will not embarrass the timeout assumptions. QuePaxa solves a problem most teams do not have.
The interesting part is the shape of the solution. Most systems that need coordination across continents avoid strong consensus entirely: AP datastores, per-region cells, control planes that reconcile eventually. A company choosing leaderless strong consensus over the public internet, rather than giving up consistency, is rare enough to be worth reading carefully. Three transferable lessons:
- Timeout-based failure detection is an assumption you are making, not a law of nature. Every system that "detects" a dead peer is really guessing at a threshold. QuePaxa removes the guess instead of tuning it.
- Interference is a design axis. In any protocol with concurrent actors, including retries, gossip and scheduler contention, ask whether a colliding message destroys work or carries information. The second design degrades; the first one stalls.
- The research shelf is underused. QuePaxa sat in ACM proceedings for three years before anyone shipped it. The algorithm for an awkward constraint may already exist, never-before-deployed, waiting for someone whose environment rules out the default choice.
Wait for the verification and benchmark posts before borrowing more than the ideas. And note Cloudflare's own framing: the less-traveled path was a consequence of constraints, not preference. If Raft fits your network model, take the boring option.
Comments