Cloudflare Meerkat picks QuePaxa consensus: 95% of decisions in one round trip

Cloudflare has chosen an unusual consensus algorithm, QuePaxa, for Meerkat, an experimental service that is meant to manage its internal global control plane. In a post dated 11 November 2026, Cloudflare engineer James Larisch explains why a company that runs servers on nearly every continent skipped Raft and Multi-Paxos, the usual choices, for a 2023 research protocol that does not depend on a stable leader. For anyone who builds or operates distributed systems, it is a rare public account of why leader-based consensus hurts on slow, uneven networks.

Key points

• Cloudflare says Meerkat, an experimental distributed consensus service for its internal global control plane, uses QuePaxa, a protocol published at SOSP 2023.
• The motivating incident: in 2020 a partial failure of a core network switch slowed a consensus-backed dashboard by 80x for six hours, with no data lost but writes unavailable.
• Cloudflare reports that upwards of 95% of Meerkat's decisions complete in one round trip under normal conditions.
• When Meerkat's leader failed in testing, the relative decision rate fell to about 65% and returned to 100% when the leader was replaced about a minute later; the system never halted.
• Cloudflare calls QuePaxa less battle-tested than Raft or Paxos, is extending it to support crash recovery, and plans formal verification.

What happened

Consensus protocols let a group of servers agree on one ordered log of events even when some servers or links fail. Most production systems use Raft, Multi-Paxos or Viewstamped Replication, all of which elect a leader to order the requests. Cloudflare's post, "Choosing QuePaxa, an unusual consensus algorithm", says it picked a different design for Meerkat, which keeps an ordered log of events and exposes applications such as a key-value store on top.

The reason is geography. Meerkat's servers span nearly all continents, over links where latency is high and varies. In that setting a leader-based protocol has a weak point: if the leader fails, slows down or is cut off, progress stalls until a new leader is elected.

Cloudflare points to its own history. In 2020, it says, a partial failure of a core network switch made a dashboard backed by consensus 80 times slower for six hours. No data was lost, but writes could not be made until the problem was resolved.

Background

Larisch lists four ways leader-based protocols struggle, in Cloudflare's description:

• Destructive interference. In Paxos, competing proposers can keep blocking one another, so liveness depends on the network being partially synchronous.
• Unstable elections. In Raft, candidates can split the vote and keep failing to win, which can turn a short outage into a metastable failure where elections keep the system down.
• Inaccurate fault detection. On an asynchronous network a slow leader looks the same as a dead one. A wrong guess triggers an unneeded election that halts progress.
• Slow fault detection. Raft's election timeout is commonly five to ten times the network round trip. A round trip around the world takes hundreds of milliseconds, so noticing a dead leader can take about a second.

QuePaxa comes from academic research: "QuePaxa: Escaping the Tyranny of Timeouts in Consensus" by Pasindu Tennage, Cristina Băsescu, Eleftherios Kokoris-Kogias, Ewa Syta, Philipp Jovanovic, Vero Estrada-Galiñanes and Bryan Ford, presented at the 29th ACM Symposium on Operating Systems Principles, 23 to 26 October 2023. The authors describe it as the first protocol offering state-of-the-art efficiency in normal operation without depending on timeouts. In wide-area experiments they report it stays live with median latency under 380 ms under conditions such as denial-of-service attacks, misconfiguration or a slow leader. They released an open-source prototype, and the paper went through SOSP's artifact evaluation.

How it works

The post's description, in our words: QuePaxa has proposers, which submit proposals, and recorders, which store every proposal they see and relay the highest-priority one. A non-leader proposer picks a random priority. The leader always holds the maximum priority. When a proposer learns of a higher-priority proposal it adopts it, so proposers cooperate instead of fighting.

Each round has four phases:

1. Phase 0, propose and adopt: priorities are sent and each proposer adopts the highest-priority proposal reported by a majority of recorders. In the first round a leader whose proposal reached a majority first decides immediately, which is the one-round-trip fast path.
2. Phase 1, spread: proposers spread their adopted proposal to a majority of recorders.
3. Phase 2, check and decide: a proposer checks whether the highest-priority proposal it saw matches its own, and decides if it does.
4. Phase 3, carry forward: proposers that have not decided adopt the best proposal from a majority and start the next round.

Safety rests on majority intersection: any two majorities share at least one recorder, so a decided value is always seen by later proposers. For liveness the paper predicts each round has a 50% chance of deciding, and Cloudflare says the practical probability is much higher because proposals converge.

Because the leader is optional, clients can send requests to any proposer. Cloudflare's design has clients send to every replica and wait a short "hedge timeout" so the leader can decide first. In its implementation the clients, not the replicas, wait out that timeout, which cuts the number of messages. The timeout is chosen locally and is not tied to network latency. A shorter timeout speeds recovery after a leader change but uses more bandwidth and raises the chance a round fails to decide.

The numbers

Cloudflare reports these results from Meerkat:

type: bar
title: Meerkat decisions under normal operation and during a leader failure (Cloudflare)
unit: %
source: Cloudflare, "Choosing QuePaxa" (11 November 2026)
Decided in one round trip, normal operation (at least) | 95
Relative decision rate during leader failure | 65
Relative decision rate after leader replaced | 100

During the leader failure, decisions shifted from Phase 0 to Phase 2. When a decision needs three round trips, Cloudflare says throughput drops to at most one third of the usual rate. The leader can be switched while the cluster is running without destabilising it. These are Cloudflare's own measurements of an experimental system, and the post does not give absolute latency figures.

What it means

For infrastructure engineers, the lesson is less "use QuePaxa" than "know what your leader costs". Leader-based consensus is simple and well understood, and its failure mode is a pause while the system works out who is in charge. For a control plane that must stay writable across oceans, that pause is the risk to design against.

For Cloudflare, Meerkat is a research-grade project. The post is explicit that QuePaxa is less battle-tested than the incumbents and that the team is extending the original crash-stop design to cope with servers that crash and recover. That is a material difference: real deployments restart machines constantly.

For the research community, a large operator publicly adopting a 2023 protocol is a useful signal, and Cloudflare plans follow-up posts on verification, failure testing, benchmarks and lessons from production.

What we don't know yet

• Meerkat is described as experimental, and we do not know whether, or when, it will carry production traffic.
• The post gives relative decision rates but no absolute latency or throughput numbers, and no comparison against a Raft deployment on the same links.
• The formal verification Cloudflare plans has not been published.
• How the crash-recovery extension changes the protocol's guarantees is not yet described.

What to watch next

Watch for Cloudflare's promised posts on verification, fault injection and benchmarks, and for whether the crash-recovery extension is published or open-sourced. If you want to experiment, the QuePaxa authors' open-source prototype and paper are linked from the authors' page below.

Sources

• Cloudflare: Choosing QuePaxa, an unusual consensus algorithm, primary source
• QuePaxa: Escaping the Tyranny of Timeouts in Consensus, ACM SOSP 2023 (DOI 10.1145/3600006.3613150)
• Paper page at bford.info
• EPFL Infoscience record