QuePaxa: Consensus Without a Single Point of Stall

Most teams building a consensus system reach for Raft or Multi-Paxos without much debate. Cloudflare's Meerkat, an experimental service for its internal global control plane, went another way. It runs on QuePaxa, a protocol published in 2023 by Tennage, Băsescu and colleagues, and the reasoning behind that choice says a lot about where classic consensus designs strain once machines are spread across continents rather than racks.

The core issue is simple to state. Familiar algorithms depend on one leader being reachable and responsive. Over a local network, that's a reasonable bet. Over the public Internet, with latency that spikes and links that drop without warning, it becomes the weak point. QuePaxa is interesting because it removes that dependency entirely, and the trade-offs it accepts are worth understanding before anyone copies the design.

Why the default designs strain on the Internet

Meerkat's job is to keep an ordered log of events on which every replica agrees. Each entry is a get or a put, and replicas that apply the same log build the same key-value state. Consensus systems like Consul, etcd and Apache ZooKeeper do the same kind of job, but they're usually deployed in tight, local clusters with strict latency budgets. Meerkat was built for the opposite case: a cluster stretched across continents, connected by links whose latency is high and changes from moment to moment.

Cloudflare has seen the failure mode directly. In 2020, the partial failure of a core network switch caused a consensus-backed system to slow dramatically. The dashboard ran 80 times slower than normal for six hours. The system lost no data, which is the guarantee consensus is supposed to provide, but it stopped accepting writes until the network issue was fixed. Cloudflare's framing is blunt: the data was safe, and the service was still unacceptable.

That distinction matters. Consensus algorithms are very good at keeping replicas from diverging. Many of them are much weaker at continuing to make progress when the network misbehaves but no machine has crashed. Under global deployment, the faults that matter most are more likely to come from the network than from servers, so a protocol that only handles crashes isn't enough.

Where Paxos-style protocols lose progress

Paxos is the ancestor of most of what's deployed today, and its structure explains both its strengths and its problems. Proposers and acceptors work through two phases. In the first, a proposer sends a numbered proposal to a majority of acceptors, promising that the acceptors will only take proposals with that number or higher. In the second, the proposer sends its actual value with that number, and if a majority still holds the promise, the value is decided.

The trouble starts when two proposers are active at once. A proposer with a higher number can slip in between another proposer's two phases and block the lower one. If both keep raising their numbers, they can block each other indefinitely. Nothing has crashed, every replica is up, and the system still makes no progress. Formally, Paxos doesn't guarantee liveness, meaning that decisions eventually happen, unless messages eventually arrive within some bounded time. That assumption is called partial synchrony, and the Internet doesn't reliably offer it.

The usual fix is to funnel all proposals through one designated leader. That removes the competition and lets decisions complete in a single network round trip rather than two. Raft, Multi-Paxos and Viewstamped Replication all work this way, and when the leader is healthy and the network is calm, they're fast. The catch is that the leader becomes a single point of stall. If it fails, slows down or gets cut off, the whole system waits until someone replaces it.

Replacing the leader can bring the interference back

Recovery is where leader-based designs get fragile. Raft picks a new leader through a majority-based process in which a replica that suspects the leader is gone becomes a candidate and asks the others to back it. If no candidate wins a majority, another round starts. Several replicas can become candidates at the same time, and they can keep splitting support between them. That is the same destructive interference seen in Paxos, now living inside the recovery mechanism.

This produces what distributed systems researchers call a metastable failure, a state that sustains itself after the original trigger is gone. Consider a two-second network disruption, or a momentarily faulty switch. The leader looks dead to the rest of the cluster, a replacement process starts, and that process can fail repeatedly because candidates keep blocking one another. The network recovers in two seconds, but the system can stay disrupted for much longer. Here's the thing: the outage that caused the problem was brief, and the recovery logic is what turned it into a lengthy one.

Fault detection is a guess in an asynchronous network

Leader replacement depends on something more basic: detecting that the leader has failed. In a distributed system, a process can't observe a remote process directly. It can only notice that an expected message did or didn't arrive on time. Heartbeats and acknowledgements establish the pattern, and a missing message triggers suspicion.

The problem is that real wide-area networks have no guaranteed upper bound on delivery time. Most messages arrive on schedule, but bursts of latency and brief connectivity losses can stretch delivery times without warning. These are asynchronous networks, and in them, a slow server and a dead server look the same from the outside. A fault detector has to make a call based on how long it has waited, and sometimes that call will be wrong.

In a leader-based protocol, a wrong call is expensive. If a replica decides the leader is faulty when it isn't, an election-style process begins and the system stops making progress until the leader is replaced. The protocol has no way to know, before it reacts, whether the leader crashed, its messages were delayed, or the connection quietly broke. Fault detection in asynchronous networks is inherently error-prone, and every mistake shows up as downtime.

Even accurate detection is slow at global distances

Suppose the detector guesses correctly every time. It still can't be faster than the network allows. A detector learns about failures by watching messages, so its timeout can't sensibly sit below the network latency. That's why Raft deployments commonly set the election timeout to five to ten times the network round-trip time. The timeout has to be long enough for a live leader to show that it's alive, or the system will trigger replacements it doesn't need.

The arithmetic gets unpleasant across oceans. A round trip between distant regions is measured in hundreds of milliseconds. A timeout spanning several of those round trips means detecting a failed coordinator can take on the order of a second. Timeouts can be set lower, but because leader replacement halts the whole system, operators usually set them conservatively. The result is that a system spread across the globe is slowest to react exactly where it's most likely to be disrupted.

What QuePaxa changes

Cloudflare's conclusion was that any design relying on a strict leader or accurate timeouts would eventually stall in a consensus system running over the Internet. The team looked for protocols built for asynchronous environments, ones that don't assume a well-behaved network or precise timing. QuePaxa was the result.

Its appeal is that it's fast when conditions are good and keeps moving when they aren't. It reaches consensus in a single round trip under favorable conditions and degrades gracefully during latency spikes, connectivity problems and server failures. QuePaxa gets there through three design decisions, each aimed at one of the problems above.

The first is an optional leader. The second is the removal of reliance on fault detection. The third is designing for constructive interference between proposers rather than competition. Each deserves a closer look, because they interact.

The protocol has two roles, much like Paxos. Proposers submit values to be decided, and recorders act as intermediaries that store every proposal they see and pass them along. The difference is in how proposers behave when they overlap.

Priorities replace competition

In Paxos, proposers fight to get their own values accepted. In QuePaxa, they cooperate toward a value everyone can support. Each proposal carries a priority, which is a random number, and the leader gets an exclusive maximum priority that no random draw can beat.

During execution, proposers send their proposals to recorders, and recorders spread those proposals to other active proposers. When a proposer receives a proposal with higher priority than its own, it adopts that proposal and starts broadcasting it instead. Over time, proposers collectively converge on the highest-priority proposal any of them knows about. Because they're adopting one another's work rather than overriding it, no proposer can lock the others out indefinitely.

Convergence isn't guaranteed in any single attempt. The spread of proposals may not be wide enough to settle on one, so proposers try again, and each attempt is called a round. The more proposers that take part, the more likely they are to land on the highest priority. That randomness is what makes QuePaxa a randomized algorithm. Random priorities are likely, though not certain, to produce agreement in a given round, and given enough rounds, agreement is guaranteed.

The leader is faster, but never required

The leader is the only proposer able to decide in a single round trip. Because it always carries the top priority, it can decide immediately if it knows its proposal reached a majority of recorders before any competitor. Any other proposer can still propose, though, so clients aren't forced to route requests through the leader. If the leader goes down, requests keep flowing to the remaining proposers. The leader is more likely to decide, and to decide faster, but the system doesn't depend on it.

That raises an obvious question: why not just let anyone propose all the time? The answer is that the leader's single-round-trip path is valuable, so the design tries to use it whenever possible without making it a single point of failure. This is where hedging comes in.

Hedging replaces fault detection

Clients send proposals to every replica, and non-leader replicas wait a short hedge timeout before acting. That gives the leader a chance to propose and decide on its own. If the leader is healthy, the fast path wins. If it isn't, other proposers are already active, and the system carries on without anyone having to declare the leader dead.

The Cloudflare team deviated slightly from the paper here. In their implementation, clients wait out the hedge timeout instead of the replicas, which reduces the number of messages on the network. The overall behavior is the same.

The important point is what this timeout is not. It isn't fault detection, so it isn't bound by network latency. Replicas set it locally, and it can be as small as they want. In Raft, a five-millisecond timeout on a network with 100-millisecond latency would freeze the system, because the timeout would fire long before any healthy leader could respond. In QuePaxa, the same five-millisecond hedge simply means more proposers are active at once. Recovery from a leader problem then becomes a matter of local tuning rather than network physics.

Hedging isn't free. More proposers mean more proposals on the wire, and a higher chance that a round fails to decide. The hedge timeout is a dial: shorten it and the system reacts faster to leader trouble, but bandwidth rises and decisions may take longer. Cloudflare says it's willing to make that trade, and for a global control plane, it's a sensible one to accept.

Inside the four phases

QuePaxa runs in rounds of four phases. At the start of each phase, proposers broadcast their current adopted proposal to all recorders. Once a proposer hears back from a majority, it moves on. If the round ends without a decision, a new round begins.

• Phase 0 (Propose and Adopt): Proposers draw a random priority, send their proposals to recorders, and adopt the highest-priority proposal they receive from a majority. In the first round, if the leader knows its proposal reached a majority first, it decides immediately.
• Phase 1 (Spread): Proposers push their adopted proposal out to a majority of recorders. Recorders remember the highest-priority proposal they've seen.
• Phase 2 (Check and Decide): Proposers ask a majority of recorders for the highest-priority proposal seen in the previous phase. If it matches what they adopted, they decide.
• Phase 3 (Carry Forward): Any proposer that didn't decide adopts the best proposal it sees from a majority of recorders and prepares for the next round.

Phase 0 does three jobs at once. It randomizes priorities, which the protocol needs in order to get around the FLP impossibility result, the theorem showing that deterministic consensus can't guarantee termination in a fully asynchronous system. It also checks whether the leader reached a majority first, and it helps proposers converge when it didn't.

The fast path works because of majority intersection. Any two majorities of recorders share at least one member. If the leader's proposal reached a majority first, any other proposer that queries a majority will hit at least one recorder holding the leader's proposal. Since the leader's priority is the highest possible, that proposer adopts it. From that point, no other value can be decided. The leader can safely decide without waiting for anyone else.

The slow path is where the design earns its keep. Take two proposers and three recorders. The leader's proposal doesn't win the race to the majority, because a second proposer reaches two of the three recorders first. Instead of fighting, the proposers adopt the highest-priority proposal they received from a majority and move to Phase 1. In principle, both could converge on the leader's proposal in Phase 0. An illustrative run might delay the leader's messages so that convergence doesn't happen in that phase.

Phase 1 is a simple but important step. The proposers spread what they just adopted, and recorders record the highest-priority proposal they see. Because majorities overlap, any majority queried later must include a recorder that saw the adopted proposal. That's what prevents the protocol from deciding on a lower-priority value down the line.

Phase 2 is where a decision can happen. Each proposer asks a majority for the highest-priority proposal observed in Phase 1. If the answer is still its own, it decides. In the walkthrough, the leader sees its own proposal come back from a majority and decides safely. The other proposer gets conflicting summaries and can't decide yet.

Phase 3 keeps the round from being wasted. The undecided proposer spreads proposals again and adopts the best one it finds in a majority of recorders. In the example, it discovers the decided value and adopts it, which means the next round starts from agreement. If a decision happened in the previous phase, a majority of recorders holds that proposal, so any remaining proposer is guaranteed to pick it up. Even a failed round leaves the proposers in a better position than they started.

After Phase 3, there's no leader fast path left in later rounds. Decisions have to come from convergence in Phase 2. Because adoption accumulates across rounds, deciding gets easier as the rounds go on. The QuePaxa paper predicts each round has a 50 percent chance of deciding. Cloudflare reports that in practice the probability is much higher, thanks to convergence.

Taken together, the phases explain the resilience. Phase 0 gives the leader its single-round-trip path. If that fails, random priorities and adoption push proposers toward agreement rather than a standoff. Phases 1 and 2 make a decision safe through majority intersection. Phase 3 carries what the proposers learned into the next round. No proposer has to decide the leader is dead before progress resumes, and a failed round doesn't discard the work already done.

What it looked like running Meerkat

Cloudflare's evaluations of Meerkat ran servers spanning nearly every continent, which is close to the hardest environment the protocol was meant for. The team reports that Meerkat keeps processing requests when the leader crashes, disconnects or simply slows down, and that it has never completely stalled. That's the property the design was chosen to deliver.

Throughput is also predictable. Upwards of 95 percent of decisions happen through the leader in the first phase, which keeps throughput fairly steady. When a decision doesn't land in the first phase, throughput drops for a moment, to at most a third of its usual rate. That slowdown corresponds to three round trips, or three phases, being needed instead of one. The system gets slower in those moments, but it doesn't grind to a halt.

QuePaxa also makes leader changes less risky while the cluster is running. Because the leader isn't the only driver of decisions and proposers cooperate, a temporarily suboptimal leader doesn't limit the system the way it would in a leader-dependent protocol, where a misconfigured leader could stall everything. Cloudflare can tune which replica acts as leader without worrying much about the cluster's stability. For operators, that's a practical benefit that often gets overlooked when people compare consensus protocols on paper.

The trade-offs and open questions

Choosing QuePaxa means choosing a path with less history behind it. Raft and Paxos have been deployed, debugged and studied for years across many production systems. QuePaxa has not been battle-tested to the same degree. Cloudflare is also extending the original crash-stop design to support crash recovery, which means the team is operating beyond what the published protocol covers. That demands more careful engineering and a higher bar for evidence of correctness than a well-worn system would need.

So Cloudflare is formally verifying its QuePaxa implementation and Meerkat as a whole, and pairing that with extensive simulation and fault-injection testing. Those techniques target failures that are hard to reproduce in production, particularly the network conditions that caused the 2020 incident. Future writing from the team is expected to cover how they verify the Rust implementation, how they test failures that rarely show up on demand, benchmarks, and what they've learned about turning an academic protocol into a production system.

My read is that the most useful takeaway isn't "use QuePaxa." It's that the usual assumptions behind leader-based consensus, namely a reachable leader, a trustworthy fault detector and a network that behaves predictably, are worth checking against your actual deployment. If your replicas sit in one rack, Raft's design is hard to beat on maturity and tooling. If they're scattered across continents and the network is the likeliest thing to fail, the cost of leader recovery and detection delays starts to dominate, and protocols that avoid those dependencies deserve a serious look. The open questions are how well randomized convergence holds up under adversarial timing, and how the crash-recovery extensions behave when they're pushed well past the original paper. Those answers will matter more to teams adopting this design than any single benchmark.