Cloudflare has recently announced the introduction of Meerkat, an experimental distributed
consensus service engineered to manage the company’s internal global control plane. At the core of Meerkat is QuePaxa, a relatively recent and unconventional consensus algorithm published in 2023 by researchers Tennage and Băsescu alongside co-authors. By adopting QuePaxa, Cloudflare is breaking away from traditional, highly established consensus systems in an effort to maintain system availability and stability across volatile, wide-area networks spanning multiple continents.
Most distributed systems rely heavily on well-understood algorithms such as Raft, Multi-Paxos, or Viewstamped Replication. These traditional protocols have mature implementations and have proven exceptionally reliable in local or regional data centers where network latency is minimal and predictable. However, running these consensus engines across the public Internet—an environment characterized by fluctuating connectivity, asynchronous routing, and high and variable latency—exposes critical vulnerabilities.
Traditional consensus algorithms typically depend on a single designated leader process to sequence operations and maintain system progress. When that leader experiences abnormal latency, disconnects, or goes down entirely, the entire consensus system generally slows down or halts writes completely until a replacement can be found and elected. For a global edge network like Cloudflare’s, such stalls are unacceptable. This operational reality prompted the engineering team to look past conventional choices and adopt QuePaxa, an algorithm designed to maintain stability and make progress even in the face of severe network volatility by not strictly relying on a single leader.
Building a Globally Scalable Consensus Log
At its technical foundation, Meerkat is a distributed system where a collection of replicas must agree upon an ordered log of events, with each entry determined by a consensus algorithm. Consensus algorithms allow a group of separate machines to agree on a single shared truth, ensuring that replicas never decide on conflicting values and that their logs never diverge. Meerkat exposes this consensus-powered log to various applications, such as a distributed key-value store where entries correspond directly to basic database operations like get and put.
Comparable consensus-powered systems frequently used in the industry include Consul, etcd, and Apache ZooKeeper. However, unlike these platforms, which are typically deployed in tightly controlled, local-area network environments with strict latency requirements, Meerkat was explicitly designed for global scale. A single Meerkat cluster can be distributed across continents, linking nodes over connections that exhibit high and unpredictable latency variations.
This global footprint introduces unique failure modes. When network conditions degrade without actual machine crashes, many traditional consensus protocols experience severe performance drops or prolonged unavailability. Cloudflare experienced this vulnerability firsthand in 2020, when a partial failure of a core network switch caused a consensus-powered system to degrade, leaving the internal dashboard operating 80 times slower than usual for six consecutive hours. Although no data was lost, the system became entirely unavailable for writes until the issue was resolved.
Ideally, a consensus algorithm should maintain progress despite latency spikes and broken connections, rather than merely surviving replica crashes. At a global scale, faults are far more likely to originate within the shared network infrastructure rather than within Cloudflare’s own servers. To understand how QuePaxa sidesteps these vulnerabilities, it is necessary to examine two common traits of traditional consensus systems: destructive interference and error-prone fault detection.
The Pitfalls of Destructive Interference and Leader Elections
To understand modern consensus limitations, one must look at Paxos, the foundational protocol that inspired many subsequent algorithms. Paxos divides processes into proposers and acceptors, where the system’s objective is for a majority of acceptors to agree on a value proposed by a proposer through a two-phase process involving a Prepare phase and an Accept phase.
Challenges arise when multiple proposers submit proposals concurrently. A competing proposer can interleave a higher ballot number between these phases, effectively blocking lower ballots. When multiple proposers repeatedly block each other, they engage in what is known as destructive interference. As concurrent proposers increase, the likelihood of the system getting stuck in endless re-proposals grows, even if zero replicas have crashed. Formally, Paxos does not guarantee liveness—meaning it cannot guarantee that proposals are eventually decided—without assuming that all messages arrive within a bounded amount of time, an assumption referred to as partial synchrony.
To prevent multiple proposers from constantly competing, most deployed algorithms like Raft and Multi-Paxos introduce a special leader proposer. The leader is the only replica permitted to make proposals, which imposes a strict order on requests, avoids competing proposals, and reduces decision-making to an optimal single network round-trip. While the leader is healthy and the network remains well-behaved, leader-based protocols are exceptionally fast.
However, this design introduces a dependency: if the leader fails, becomes too slow, or loses connectivity, the system stalls. The remaining replicas must detect the failure and elect a new leader. Unfortunately, leader recovery frequently reintroduces destructive interference. In Raft, for instance, replicas suspecting a leader failure announce themselves as candidates and request majority votes. When multiple replicas do this simultaneously, their election campaigns collide, preventing any single candidate from securing a majority.
Even after the original network issue subsides, elections can continue to disrupt normal operations, triggering what is known as a metastable failure—a failure pattern that perpetuates itself long after the initial cause has been removed. A brief two-second network glitch can force a leader election that subsequently fails and triggers further cascading elections, extending downtime far beyond the duration of the original network outage.
The Challenges of Fault Detection in Wide-Area Networks
The problem of destructive interference during leader elections is compounded by trigger-happy fault detection. In a distributed system separated by wide-area networks, a process cannot directly observe that a remote machine has failed; it can only observe that an expected message has or has not arrived within a certain timeframe.
In real-world networks, messages do not always arrive on a predictable schedule, and there is no guaranteed upper bound on transit times. When a server fails to reply within a predetermined window, the system cannot easily distinguish between a genuine server crash and a temporary network slowdown. Consequently, practical fault detectors must guess based on waiting times, and those guesses are occasionally wrong.

When a fault detector mistakenly assumes a healthy leader has failed, it triggers an unnecessary election, forcing the entire system to halt until a new leader is established. Furthermore, to avoid false positives, fault detectors must set conservative timeouts scaled to network latency. In high-latency global networks, detecting a failed coordinator can take up to a full second or more, during which the system remains completely unavailable for writes.
Why QuePaxa Fits Global Infrastructure
Recognizing that any algorithm relying on strict leaders or accurate timeouts would inevitably stall over the Internet, Cloudflare searched for protocols designed specifically for asynchronous environments. This search led them to QuePaxa.
The defining characteristic of QuePaxa is its ability to reach consensus efficiently in a single round trip under favorable network conditions, while gracefully degrading performance during latency spikes, connectivity issues, and server failures. QuePaxa achieves this resilience through three primary design choices: employing an optional leader, completely eliminating reliance on traditional fault detection, and engineering for constructive interference among proposers.
Similar to Paxos, QuePaxa utilizes proposers and recorders, where recorders serve as intermediaries that record every proposal they encounter. Rather than competing to push their own proposals through, proposers in QuePaxa work cooperatively toward a universally supported proposal by assigning a randomized priority to each submission. The optional leader is assigned an exclusive maximum priority.
During execution, proposers submit proposals to recorders, which propagate them to other active proposers. When a proposer receives a proposal with a higher priority than its own, it adopts the higher-priority proposal and begins broadcasting it instead. Proposers continually collaborate to decide on the highest-priority proposal they collectively know, preventing any single proposer from locking out others indefinitely.
While the algorithm relies on randomized priorities to escape theoretical impossibility theorems like FLP, repeated rounds guarantee that proposers eventually converge. Although one proposer is designated as the leader to enable a fast path that decides in a single round trip, that leader is completely optional. If the leader goes down, clients can continue making requests to any other proposer without waiting for a formal leader election.
To capture the benefits of the fast path without creating a single point of failure, clients hedging their bets send requests to every replica. Non-leader replicas wait for a short hedging timeout to allow the leader to propose and decide on its own. In Cloudflare’s specific implementation, clients manage this hedging timeout directly to minimize unnecessary network messaging.
Crucially, this hedging timeout is distinct from traditional fault detection. It is not constrained by network latency and can be set locally to small values. If a hedging timeout is short, it merely increases the number of active proposers rather than freezing the system. If the QuePaxa leader fails, the system recovers instantly without being bound by network timeout delays.
Operating Principles and Real-World Performance
QuePaxa executes in rounds composed of distinct phases. At the start of each phase, proposers broadcast their currently adopted proposal to all recorders, advancing once they receive replies from a majority.
In Phase 0, priorities are randomized—except for the leader’s maximum-priority proposal—and the system checks if the leader can achieve a fast-path decision via majority support. Thanks to majority intersection, any two majorities of recorders always share at least one node, ensuring that if the leader reaches a majority, any subsequent proposer querying a majority will inevitably encounter and adopt the leader’s proposal.
When concurrent proposers contest the leader, the fast path is bypassed, initiating a slower path through subsequent phases. In Phase 1, proposers spread their adopted proposals to a majority of recorders. In Phase 2, proposers verify whether a higher-priority proposal gained enough support to overtake their own, allowing safe decisions if summaries align. Phase 3 acts as a cleanup phase, ensuring that any unresolved proposers adopt the best proposal found among recorders before heading into the next round. This mechanism guarantees that failed rounds never discard prior progress.
Cloudflare’s real-world evaluations of Meerkat across servers spanning nearly all continents have confirmed the practical efficacy of this design. The system processes requests continuously, even when the leader crashes, disconnects, or experiences latency spikes, with zero instances of complete system stalls.
Request handling throughput under normal operation remains high, with upwards of 95% of decisions made by the leader in the first phase. In instances where a decision requires multiple phases, throughput drops momentarily to a fraction of its usual rate as the system processes the slower path, but the infrastructure continues to move forward without grinding to a halt. Furthermore, the optional nature of the leader allows operators to switch active leader roles dynamically in a running cluster without impacting overall cluster stability.
Choosing QuePaxa required taking an unconventional path compared to battle-tested defaults like Raft or Paxos. Because the original academic design focused primarily on crash-stop failure models, Cloudflare’s engineering team has extended the implementation to support full crash recovery, backed by formal verification, extensive simulation, and fault-injection testing. Future updates from Cloudflare are expected to detail the formal verification of the Rust-based implementation and share further insights derived from turning an academic protocol into a globally deployed production system.