Cloudflare is building Meerkat, an experimental distributed consensus service for its global control plane, using the QuePaxa consensus algorithm. Common leader-based algorithms like Raft and Paxos degrade under volatile network conditions because they stall when the leader becomes unreachable or slow. QuePaxa is leaderless, allowing any proposer to drive decisions without a single point of failure. Proposers cooperate by using a shared data structure to track pending ballots and back off when they detect contention, preventing the destructive interference that causes metastable failures. Cloudflare is formally verifying its Rust implementation of QuePaxa and plans to share benchmarks and lessons learned in future posts.
Context
Cloudflare is building Meerkat, an experimental distributed consensus service for its internal global control plane. Meerkat runs across continents over the public Internet, where links exhibit high and variable latency. Common leader-based algorithms like Raft and Paxos degrade under such conditions because they stall when the leader becomes unreachable or slow, and leader elections can trigger metastable failures. QuePaxa was chosen because it does not rely on a single leader and can make progress despite network volatility.
Approach / What changed
QuePaxa is a leaderless consensus algorithm that allows any proposer to drive decisions without a single leader, avoiding destructive interference and fault-detection stalls. Proposers cooperate by using a shared data structure (a ‘window’) to track pending ballots, and they back off when they detect contention, which prevents the metastable failures common in leader-based systems. The algorithm guarantees liveness under weaker synchrony assumptions than Paxos or Raft, making it suitable for wide-area networks with volatile latency and connectivity.
Takeaways
1
QuePaxa is a leaderless consensus algorithm that avoids the destructive interference and metastable failures common in leader-based algorithms like Raft and Paxos under volatile network conditions.
2
Proposers in QuePaxa cooperate by using a shared data structure (a ‘window’) to track pending ballots and back off when they detect contention, which prevents repeated election failures.
3
Cloudflare is formally verifying its Rust implementation of QuePaxa and extending the original crash-stop design to support crash recovery, alongside extensive simulation and fault-injection testing.
FAQ
How does QuePaxa differ from Raft or Paxos?
QuePaxa is a leaderless consensus algorithm that allows any proposer to drive decisions without a single leader. Proposers cooperate by using a shared data structure (a 'window') to track pending ballots, and they back off when they detect contention, which prevents the destructive interference and metastable failures common in leader-based systems like Raft or Paxos.
What liveness guarantees does QuePaxa provide?
QuePaxa guarantees liveness under weaker synchrony assumptions than Paxos or Raft. It does not require a leader to be reachable or a bounded message delay to make progress, so it can continue operating even when network latency spikes or connections are broken, as long as a majority of acceptors are reachable.
What are the risks of using QuePaxa?
QuePaxa is less battle-tested than Raft or Paxos, and Cloudflare is extending its original crash-stop design to support crash recovery. This requires careful engineering and formal verification of the Rust implementation, alongside extensive simulation and fault-injection testing.
ARC Region Switch is a managed failover orchestrator that runs team-owned plans in dependency order. This diagram maps its trigger, orchestration, execution, and region layers and the ownership boundary.
Keep reading
Related reading
The Good Stuff
Paid picks we use ourselves. Links carry a referral code — a subscription through one earns us a commission at no extra cost to you.