QuePaxa Consensus Keeps Global Systems Moving Through Network Delays
- Cargo
- Machine Learning
- Shipped
- Shipper
- João Pedro Leite
- Readers
- 576
Meerkat uses QuePaxa to keep deciding requests through latency spikes and leader failures, with a fast path for normal conditions and extra network cost under contention.

Meerkat’s choice of consensus algorithm reflects a hard constraint of global systems: a slow or unreachable coordinator can stall a service even when most machines are healthy. Cloudflare built Meerkat, an experimental service for its internal global control plane, around QuePaxa, a consensus algorithm published in 2023 by Tennage & Băsescu and colleagues. QuePaxa gives the system a fast path when the network behaves, while allowing other proposers to keep working when the leader is slow or disconnected.
That design targets a familiar weakness in consensus protocols. Systems such as Raft, Multi-Paxos and Viewstamped Replication can perform well in predictable networks, but their progress often depends on a single leader and timely messages. Across continents, latency can vary and links can break temporarily. A leader may appear to have failed when it is merely slow, and replacing it can take longer than the network problem that triggered the recovery.
QuePaxa takes a different approach: the leader is useful, but not required for progress. Other replicas can submit proposals, and the protocol encourages them to converge on the same proposal instead of competing to establish separate ones. In Meerkat’s reported evaluations, more than 95% of decisions were made by the leader in the first phase. When that fast path did not complete, throughput fell temporarily to at most one third of its usual rate, but the service continued processing requests.
Why global placement changes the consensus problem
Meerkat replicas agree on an ordered log of events. Each decided event is added to that log, and replicas use the same sequence to build their application state. A key-value store is one example: log entries can represent get and put operations. If the replicas agree on the order and contents of the log, they can construct matching key-value states.
This is the same basic model used by systems such as Consul, etcd and Apache ZooKeeper. Meerkat’s distinctive constraint is its intended geography. Its replicas may span continents, with network links that have high and changing latency. Many consensus deployments operate across smaller, more local networks, where latency expectations are easier to meet. A global service has to account for delays and brief connectivity failures as routine operating conditions, rather than unusual events.
Consensus provides a safety guarantee: replicas do not decide conflicting values. That guarantee is separate from liveness, the ability to keep deciding values over time. A protocol can preserve data perfectly while becoming unable to accept writes. Cloudflare experienced that distinction in 2020, when a partial failure of a core network switch left a consensus-powered system without data loss but unable to process writes. The dashboard ran 80 times slower than usual for six hours. The incident showed why preserving consistency is not enough for a service that needs to remain available through network trouble.
In a wide-area network, a replica can be alive and still be unreachable for a time. Messages may arrive late, or not at all during a short disruption. Protocols that need a stable coordinator or dependable timing can respond to these conditions by pausing work while they decide what happened. QuePaxa is designed to let proposals continue despite that uncertainty.
How leaders can become a bottleneck
Paxos provides a useful starting point for understanding the issue. In simplified terms, it has proposers that put forward values and acceptors that record them. A proposer first sends a numbered ballot to a majority of acceptors in a Prepare phase. The ballot establishes a promise: those acceptors will not accept a lower-numbered proposal. The proposer then sends its value and ballot number in an Accept phase. If a majority still accepts that ballot, the value can be decided.
The protocol has to handle competing proposers. Suppose one proposer starts with a ballot number, then another sends a higher number before the first has completed both phases. Acceptors that have promised the higher number will reject the earlier ballot. The first proposer may have to start again with a higher number, only to be interrupted by yet another proposer. Each attempt can invalidate progress made by another.
This is destructive interference: independent proposers repeatedly block one another. The risk grows with the number of concurrent proposers, especially when message delays make their actions overlap. Even if no machine has crashed, the system may struggle to decide a value. In the formal model, Paxos does not guarantee liveness without an assumption that messages eventually arrive within a bounded time. That condition is called partial synchrony.
Many deployed protocols reduce this competition by restricting proposal power to one leader. Raft, Multi-Paxos and Viewstamped Replication use this pattern. A single proposer orders requests, avoiding clashes between multiple ballot attempts. When the leader is healthy and messages arrive as expected, this also supports a fast path: decisions can be made in one network round trip rather than the two phases of basic Paxos.
Centralizing proposals has a cost. The leader must remain reachable and responsive. If it becomes slow, disconnects or crashes, replicas cannot simply carry on as before. They must identify a replacement. Until then, the system’s progress is limited or stopped.
Recovery can prolong a brief disruption
Raft illustrates how recovery can reintroduce the very competition that a leader is meant to prevent. When replicas suspect that the leader is unavailable, one or more may become candidates and ask the others for support. A candidate needs a majority to become the new leader. If no candidate gets that support, another attempt begins.
Several replicas can suspect a problem at the same time. They may then seek the same majority simultaneously, dividing support and preventing any one candidate from taking over. Repeated failed attempts can make more replicas try. The service can remain caught in recovery even after the original network delay has passed. This self-perpetuating pattern is known as a metastable failure: an initial disturbance triggers activity that continues to disrupt the system after that disturbance ends.
A short network outage can therefore have a longer effect. A two-second interruption may make a healthy leader appear unreachable. If that triggers unsuccessful recovery attempts, those attempts can continue after connectivity returns. Recovery logic adds another way for the system to lose time, and its behavior depends on how replicas interpret incomplete information.
That interpretation is inherently uncertain. A replica cannot directly inspect a remote machine to determine whether it has failed. It can observe only what arrives over the network. Systems use regular messages, such as heartbeats or acknowledgements, to indicate that a process is responsive. If an expected message does not arrive by a chosen deadline, the observer suspects a failure.
In an asynchronous network, there is no guaranteed maximum delivery time. Most messages may arrive within the expected interval, yet an unexpected delay or broken link can make a healthy process look unavailable. A timeout cannot reliably distinguish a failed machine from a late message. Any practical failure detector must make a judgment based on elapsed time, and sometimes that judgment will be wrong.
For a leader-based protocol, a mistaken suspicion can halt ordinary work and trigger recovery. The system may pause while replicas attempt to replace a leader that was still functioning. Even an accurate suspicion has a latency cost: the detector must wait long enough for the expected message to have had a reasonable chance to arrive.
Raft’s election timeout is commonly set to five to ten times the network round-trip time, according to the etcd tuning documentation. A timeout set too low risks falsely suspecting a healthy leader; a conservative timeout reduces that risk but delays the response to a real failure. Across a long-distance network, a round trip can take hundreds of milliseconds, so waiting through several round trips can put detection on the scale of a second. During that wait, the system may not make progress.
QuePaxa makes the leader optional
QuePaxa addresses these problems with three linked choices: it makes the leader optional, avoids depending on failure detection, and arranges for proposers to help one another converge. The algorithm was published in 2023 by Tennage & Băsescu and colleagues. Like Paxos, it uses proposal-making processes, called proposers, and processes that record proposals, called recorders.
Each proposal has a priority represented by a random number. The leader receives the highest possible priority, while other proposers use randomly generated priorities. Proposers send their proposals to recorders, which keep track of what they have seen and pass proposals to active proposers. When a proposer learns of a higher-priority proposal, it adopts that proposal and begins sending it onward.
This changes the incentives between concurrent proposers. They are not trying to lock one another out by repeatedly raising competing ballots. Instead, each can adopt the highest-priority proposal it learns about. A round may fail to spread proposals widely enough for a decision, but proposer activity tends to move toward a shared value. Random priorities make agreement likely within a round, not certain; the protocol guarantees that proposers agree given enough rounds.
The leader remains valuable because its highest priority gives it a chance to decide in a single round trip. If it can establish that its proposal reached a majority of recorders before any competing proposal, it can use the fast path. But clients can send requests to any proposer. If the leader is unavailable, other proposers can keep trying without waiting for a detector to declare the leader failed.
Meerkat’s implementation uses a hedge to preserve the fast path without making the leader a single point of failure. Clients send requests for proposals to every replica. The implementation deviates from the QuePaxa paper in where it applies the hedge delay: clients wait for the short timeout, while non-leader replicas wait in the paper’s design. This reduces the number of messages Meerkat sends while keeping the same basic outcome. If the leader responds within the interval, it can decide quickly; otherwise, other proposers enter the work.
The hedge timeout is not a failure detector. It does not claim that the leader has crashed, and its duration does not have to account for the distance between replicas. A short delay can be used even when network round trips are long. If the leader has not made progress by then, the system simply adds more active proposers.
That flexibility has a price. More proposers mean more proposals broadcast across the network, increasing bandwidth use and the chance that a round will not reach a decision. A shorter hedge can reduce the wait before other proposers act, but the added traffic may make decisions take longer. Meerkat’s design accepts this tradeoff to avoid waiting on a possibly stalled leader.
Four phases turn cooperation into a decision
QuePaxa organizes work into rounds, each with four phases. At the start of a phase, proposers send their currently adopted proposal to recorders. A proposer moves on after hearing from a majority. If it has not decided by the final phase, it begins another round with the best proposal it has learned. The phases are built to preserve safety while carrying useful information forward.
- Phase 0, Propose and Adopt: Proposers choose priorities and send proposals to recorders. They adopt the highest-priority proposal reported by a majority. In the first round, the leader can decide immediately if it knows its proposal reached a majority first.
- Phase 1, Spread: Proposers send the proposal they adopted to a majority of recorders, giving the value broader support.
- Phase 2, Check and Decide: Proposers ask a majority of recorders for the highest-priority proposal seen in the previous phase. A proposer decides if that proposal matches its own adopted value.
- Phase 3, Carry Forward: Proposers that did not decide gather the best proposal reported by a majority and adopt it for the next round.
The fast path depends on majority intersection. Any two majorities drawn from the same group of recorders share at least one recorder. If the leader’s proposal reaches a majority first, another proposer querying a majority must encounter a recorder that saw it. Because the leader’s proposal has the highest priority, the other proposer must adopt it. That overlap prevents a conflicting value from being decided.
When another proposer reaches recorders first, the leader may not be able to decide immediately. The protocol then relies on adoption and spreading rather than competition. In Phase 0, proposers compare what a majority has reported and adopt the highest-priority proposal they learn about. They may converge at this point. If messages arrive unevenly, they may not; the following phases retain the information needed to make a safe decision later.
Phase 1 records the adopted proposals across a majority. That step matters because a proposer in Phase 2 will query another majority, which must overlap with the one reached in Phase 1. At least one recorder in the later query has therefore seen a proposal spread in the earlier phase. This limits the possibility of deciding on a lower-priority value after a higher-priority one has gained the necessary support.
In Phase 2, each proposer checks the recorders’ accounts of what they saw in Phase 1. If the highest-priority proposal returned by a majority matches the proposer’s adopted proposal, it can decide. Different proposers may receive different information when messages are delayed, so one may decide while another must continue. The protocol does not require every proposer to reach a decision at the same moment.
Phase 3 helps those still working catch up. A proposer that did not decide asks a majority for the best proposal and adopts it before the next round. If a value was decided in the prior phase, a majority of recorders will have that value. Any proposer querying a majority will encounter it, again because majorities overlap, and must carry it forward.
After the first round, the leader’s special fast path is gone. Decisions depend on proposers converging during the later phases. But a failed round is not wasted: proposers retain what they learned, making agreement more likely in subsequent rounds. The QuePaxa paper predicts a 50% chance of deciding in each round; Meerkat’s account says practical odds are higher because adoption helps proposals converge.
What Meerkat reports in its evaluations
Cloudflare says it evaluated Meerkat with servers spanning nearly all continents. In those evaluations, the system continued handling requests when the leader crashed, disconnected or became slow. The team reports that it had not seen the system stall completely. That result speaks directly to the design goal: loss of the leader’s fast path did not require the entire cluster to wait for replacement before processing work.
Most decisions—more than 95%—were made by the leader in the first phase. That kept throughput fairly stable under the evaluated conditions. When a decision did not complete in that phase, throughput temporarily dropped to no more than one third of its usual rate. The reported explanation is that those cases needed three round trips, or three phases, to decide rather than one.
These figures describe the team’s evaluations, not a universal performance guarantee. The account does not provide a workload description, an absolute throughput figure, latency percentiles or a direct benchmark comparison with Raft or Paxos. Those details would be needed to judge how the results translate to another deployment. The reported availability behavior and fast-path share are useful signals, but they do not by themselves establish how the system performs under every network pattern or workload.
QuePaxa also makes it easier to change which replica acts as leader while the cluster runs. Since other proposers can keep working, a temporarily poorly placed or slow leader is less likely to stop the system. Meerkat can tune the leader assignment without relying on that one replica as the sole source of progress.
Engineering work remains
QuePaxa is less widely exercised than Raft or Paxos. Meerkat also extends the paper’s original crash-stop design to handle crash recovery, where a process can restart and rejoin after failing. That extension adds implementation and correctness questions: the system must preserve the protocol’s guarantees when replicas return, not only when failed processes remain gone.
Cloudflare says it is formally verifying both its QuePaxa implementation and Meerkat, alongside simulation and fault-injection work. Those methods can help examine behaviors that are difficult to reproduce consistently in production, especially failures involving timing, message loss and recovery. The team has also said it plans to share benchmarks and details about verification and testing.
For engineers considering consensus across long-distance links, the key design question is whether the system can make progress when timing assumptions fail. QuePaxa trades additional proposal traffic and more complex implementation work for a protocol that can continue without first deciding whether its leader has failed. Meerkat’s results suggest that this trade can preserve a fast common path while limiting slowdowns during disruption; the forthcoming benchmark and verification details will show how well that behavior holds across workloads and failure patterns.