Cloudflare Chooses QuePaxa for Experimental Meerkat Consensus Service

Cloudflare has announced Meerkat, an experimental distributed consensus service designed to manage its internal global control plane. The service is powered by QuePaxa, a 2023 consensus algorithm by Tennage and Băsescu et al. Cloudflare says the choice targets better stability in wide-area networks with volatile latency and connectivity.

Why common algorithms fall short

Meerkat replicas agree on an ordered log of events, and each event is decided by consensus. Comparable systems include Consul, etcd, and Apache ZooKeeper, but Meerkat is designed for global scale across continents. Common algorithms such as Raft, Multi-Paxos, and Viewstamped Replication rely on a single leader and predictable latency. If the leader fails, slows, or disconnects, the system can stall until a new leader is elected.

QuePaxa's design

QuePaxa uses proposers and recorders. Proposers cooperate toward the highest-priority proposal, using randomly assigned priorities; one optional leader always proposes with the highest priority. It can decide in a single round trip under favorable conditions, while degrading gracefully during latency spikes, connectivity issues, and server failures. The algorithm removes reliance on fault detection and avoids destructive interference by having proposers adopt higher-priority proposals.

How rounds work

QuePaxa works in rounds of four phases: Propose and Adopt, Spread, Check and Decide, and Carry Forward. In Phase 0, proposers may decide immediately if the leader reaches a majority first. In Phase 2, a proposer decides if the highest-priority proposal returned by a majority still matches its adopted proposal. If not, Phase 3 prepares remaining proposers for the next round. Clients hedge by sending requests to every replica, letting non-leader replicas wait briefly so the leader can act first.

Sources: Cloudflare