Cloudflare bets on QuePaxa for a global consensus service
Most distributed systems that need agreement reach for the same handful of algorithms: Raft, Multi-Paxos, Viewstamped Replication. They are well understood, widely implemented, and battle-tested in production. Cloudflare looked at all of them and chose something else. Its experimental consensus service, Meerkat, runs on QuePaxa, a 2023 algorithm that has never been deployed at production scale. The reasoning is a useful case study in what breaks when consensus leaves the data center.
Meerkat is a distributed system whose replicas agree on an ordered log of events. Applications built on it, such as a key-value store, treat each log entry as a get or a put. Because the log never diverges, every replica reconstructs the same state. That is the same shape as Consul, etcd, and ZooKeeper. The difference is geography: a Meerkat cluster can span continents, connected by links with high and variable latency.
Why leader-based consensus struggles at global scale
Classic consensus algorithms are usually deployed on small, local networks with strict latency expectations. Raft, for example, is commonly tuned with an election timeout of five to ten times the network round-trip time. That works when round trips are sub-millisecond. Halfway around the world, a round trip is measured in hundreds of milliseconds, so detecting a failed leader can take around a second. Until the detector reacts, the system makes no progress.
Cloudflare has seen this failure mode firsthand. In 2020, a partial failure of a core network switch degraded a consensus-powered system and made the dashboard operate 80 times slower than usual for six hours. No data was lost, but writes were unavailable until the problem was resolved. That is the behavior Meerkat is designed to avoid. At global scale, the fault is more likely to be in the network than in the machines, and the algorithm should keep going anyway.
The core issue is that Raft, Multi-Paxos, and Viewstamped Replication all depend on a single leader. Centralizing proposals forces an order on concurrent requests and lets the leader decide in one network round trip while it is healthy. The trade-off is that the leader must remain reachable. When it stalls or disconnects, the whole cluster stalls until a new leader is elected.
Destructive interference and the election trap
Paxos, the ancestor of most of these algorithms, has two phases: prepare and accept. A proposer sends a ballot number to a majority of acceptors, then sends its proposal. If a second proposer interleaves a higher ballot between those phases, the first proposal is rejected. Two proposers can keep blocking each other indefinitely. This is destructive interference, and it gets worse as more proposers participate.
Leader-based algorithms add a leader to avoid that competition. But the competition reappears during leader recovery. When a leader fails, any replica can declare itself a candidate. Several candidates may campaign at once, splitting the vote so that no one wins. Failed elections encourage more candidates, which causes more failed elections. This is a metastable failure: a pattern that sustains itself even after the original trigger is gone. A two-second network blip can force an election that keeps churning long after the blip ends.
Fault detection compounds the problem. A process cannot observe that a remote process has died; it can only observe that an expected message has not arrived. In an asynchronous network there is no upper bound on message delay, so a slow response and a crashed server look identical. Any practical detector has to guess based on elapsed time, and sometimes the guess is wrong. When it is wrong, the cluster starts an election and stops serving requests even though the leader was healthy all along.
How QuePaxa works
QuePaxa, published by Tennage and Băsescu et al. in 2023, attacks all three problems at once. It has an optional leader rather than a required one, it removes reliance on fault detection, and it turns proposer competition into cooperation. The paper describes proposers and recorders. Proposers submit values; recorders act as intermediaries and record every proposal they see.
Each proposal carries a random priority. The designated leader gets an exclusive maximum priority. Proposers send their proposals to recorders, and the recorders propagate proposals to other active proposers. When a proposer hears a proposal with a higher priority than its own, it adopts that proposal and starts broadcasting it instead. Instead of locking each other out, proposers converge on the highest-priority proposal they collectively know. The randomness is essential: it is how the protocol sidesteps the FLP impossibility result, which says no deterministic algorithm can guarantee both safety and liveness in a fully asynchronous network.
Execution proceeds in rounds of four phases. In phase 0, proposers pick a priority, send proposals, and adopt the highest-priority proposal they see from a majority of recorders. If the leader can confirm that its proposal reached a majority first, it decides immediately in one round trip. In phase 1, proposers spread the adopted proposal to a majority of recorders. In phase 2, they ask a majority which proposal had the highest priority in the previous phase; if the answer matches their own, they decide. In phase 3, anyone who did not decide adopts the best proposal it can find and carries it into the next round.
Safety comes from majority intersection. Any two majorities of recorders share at least one member. If the leader's proposal reached a majority, any other proposer querying a majority will encounter it and adopt it, and because the leader's priority is maximal, no lower-priority proposal can win. That is what makes the one-round-trip fast path safe.
The hedge timeout is not a fault detector
The leader still matters because it is the only proposer that can decide in a single round trip. To use that fast path without creating a single point of failure, clients hedge: they send requests to every replica, and non-leader replicas wait a short timeout so the leader can decide first. Cloudflare's implementation deviates slightly from the paper by having clients wait the hedge timeout instead of replicas, which reduces network traffic, but the effect is the same.
The important property is that the hedge timeout is not fault detection. It is not constrained by network latency; it is a local choice that can be as small as the operator wants. In Raft, a five-millisecond timeout on a network with 100-millisecond latency would freeze the system. In QuePaxa, a five-millisecond hedge timeout merely increases the number of active proposers. Lowering it lets the cluster react faster to a leader change, at the cost of extra bandwidth and a higher chance of needing another round. That is a trade Cloudflare says it is happy to make.
The result is that leader failure does not require a recovery protocol. Any replica can propose, so the system deals with a bad leader proactively rather than reacting after a detector fires. There is no election, no campaign, and no metastable failure loop.
What Cloudflare has observed in Meerkat
Cloudflare has run Meerkat across servers on nearly every continent. In its own evaluation, the service kept processing requests when the leader crashed, disconnected, or slowed down, and never completely stalled. When a leader failed, the relative decision rate fell to around 65 percent and recovered to 100 percent when a replacement was established about a minute later. The system slowed down; it did not stop.
Most decisions, upwards of 95 percent, are made by the leader in phase 0, which keeps throughput stable. When a decision is not reached in the first phase, throughput drops to at most a third of the usual rate because three round trips are needed instead of one. Cloudflare can also switch which replica acts as leader while the cluster is running, because the leader is not the exclusive driver of decisions.
The trade-off is that QuePaxa is not battle-tested like Raft. Cloudflare is extending the original crash-stop design to support crash recovery, which the paper does not cover. It is formally verifying its implementation and running simulation and fault-injection tests. Those are the right instincts. A novel consensus algorithm is exactly the kind of code where "it worked in the lab" is not enough, and the company is treating the lack of production history as a risk to retire deliberately.
Why the implementation language matters
Cloudflare is writing Meerkat and QuePaxa in Rust, and the choice is not incidental. Consensus code is concurrent, pointer-heavy, and full of state machines that must remain correct across crashes and message reordering. Those are exactly the conditions where memory-safety bugs are most dangerous and hardest to reproduce. A use-after-free in a message handler can corrupt the log or crash a replica at the worst possible moment, and a data race can violate an invariant that the protocol proof assumes holds.
Rust doesn't make it correct. The safety proof still boils down to maths of message and majority. The implementation itself can still be buggy (logically). But it does remove a set of failure modes that would otherwise be lurking under the proof. It also makes the concurrency model explicit enough that you can reason about shared state and owned state per task. It's a huge win if you're already rolling the dice on an unproven algorithm to have fewer independent failure modes.
But it comes at the cost of having a Rust ecosystem for formal verification that's less mature than for C/Java. They're saying they're formally verifying the implementation. So there's a model of the protocol (outside code) and a verification that code refines the model. That's a lot of work. And it's the sort of thing that's easy to say you're doing but hard to actually achieve. You have to see that they'll be keeping up with the verification effort as much as the implementation. It's not just the language.
Another less obvious win is that it's easier to run the code both in simulation and in production. Cloudflare has a testing plan that involves deterministic simulation and fault injection. So it's more likely that the code in simulation is the same as the code in production when you have a language that's strongly typed and without undefined behavior. That's important when you have a protocol that's timing dependent and dropping messages. A test harness that's different than production is worse than no test harness.
The broader lesson
The interesting thing about Meerkat isn't the fact that Cloudflare chose some obscure algorithm. It's that they chose it based on a clear definition of their environment. They didn't ask "what's the best consensus algorithm in general?" Instead they asked "what's the algorithm that's making progress through spikes in latency and broken links?" Because that's what they're running on. Raft/Paxo are great solutions to a different question where the network is fast. And failures are mostly just crashes.
So steal that. So much of the infrastructure decisions default to the familiar. And then they build up workarounds for things that the familiar does poorly. But instead Cloudflare's willing to pay the price of an unproven protocol. And match it with unusually high verification. It's less important if QuePaxa becomes a popular choice. But it's important to steal the technique. Define the failure model. Then choose your algorithm to match the model.
Conclusion
QuePaxa is a bet that global scale consensus should degrade gracefully rather than grinding to a halt. The optional leader, random priorities, cooperative proposal adoption. They're trading elections and fault detectors for hedging and convergence. Based on initial numbers from Cloudflare. It looks like they're hitting their main promise. Meerkat slows down in the presence of leader failure. But it still makes decisions. The question is whether they'll have enough formal verification and fault injection to trust the protocol with so little production history. If you're on a team that's building control planes that span continents. You should read the Meerkat writeup. As much to understand how they chose it as what algorithm they ended up with.
Sources
- Cloudflare, "Choosing QuePaxa, an unusual consensus algorithm": https://blog.cloudflare.com/choosing-quepaxa/
- Meerkat introduction: https://blog.cloudflare.com/meerkat-introduction/
- Tennage and Băsescu et al., QuePaxa (2023): https://dl.acm.org/doi/10.1145/3600006.3613150
- Cloudflare, "A Byzantine failure in the real world": https://blog.cloudflare.com/a-byzantine-failure-in-the-real-world/