QuePaxa: An Unusual Consensus Algorithm and Why Cloudflare Chose It

In this article
Why global-scale consensus is hard
A consensus algorithm lets a group of machines agree on one shared truth even when some machines crash or lose connectivity, and guarantees that the machines never commit conflicting values. Meerkat relies on such an ordered log to serve applications like a key-value store, in which each log entry is a get or a put; because the log does not diverge, every replica builds the same state. Consul, etcd and Apache ZooKeeper are similar systems. Unlike them, a Meerkat cluster can span multiple continents, across high-latency, variable links, whereas consensus systems typically run on small, local networks with tight latency requirements.
Many algorithms become disproportionately slow or unavailable when network conditions worsen, even if no machine crashes. In 2020, a partial failure of a Cloudflare core network switch degraded a consensus-based system, and a dashboard ran 80x slower than normal for six hours. The system lost no data but could not write until the incident was resolved.
Two weaknesses: destructive interference and fault detection
Paxos has two roles, proposer and acceptor, and two phases, Prepare and Accept. In the Prepare phase, a proposer sends a ballot number to a majority of acceptors; in the Accept phase, it sends a proposal carrying that ballot number, and if the majority still holds that ballot, the proposal is accepted. When multiple proposers are active at the same time, one proposer can slip a higher ballot between the two phases, blocking lower ballots. This repeated mutual blocking is called destructive interference, and the more proposers there are, the more likely it is, even if no replica crashes.
To avoid contention, Raft, Multi-Paxos and Viewstamped Replication add a single leader that has the exclusive right to propose. This forces an order on concurrent requests and lets a decision be committed in one network round trip instead of two. The cost is that the leader must always be running and reachable; if it fails, is too slow or gets disconnected, the system stalls until a new leader is elected. The re-election process itself can bring destructive interference back: in Raft, candidates compete for a majority of votes and can block one another.
The consequence is a metastable failure: a kind of failure that persists even after the original cause has disappeared. A two-second network incident can make the leader look faulty, trigger an election, the election fails and then triggers further elections, lasting far longer than the original incident.
How QuePaxa solves the problem
QuePaxa reaches consensus in one round trip when the network is favorable, but degrades gracefully when there are latency spikes, connectivity problems or server failures. It achieves this through three design choices.
The leader is optional: any proposer can propose.
It eliminates the dependency on failure detection entirely.
It is designed so that proposers interfere constructively, that is, they cooperate instead of competing.
QuePaxa has two roles: proposers, which make proposals, and recorders, which act as intermediaries and record every proposal they see. Each proposal carries a priority that is a random number, and only the optional leader always has the highest priority. On receiving a proposal with a higher priority than its own, a proposer switches to broadcasting that proposal, so the proposers converge on the highest-priority proposal known to the group and cannot lock each other out indefinitely. Because of the randomness, this is a randomized algorithm: converging within a round is very likely but not certain, and if it does not happen, it retries in a new round, but given enough rounds the proposers are guaranteed to reach agreement.
The hedge timeout is entirely different from the timeouts in Raft or Multi-Paxos: it is not failure detection, so it is not bound by network latency, since each replica decides it locally and it can be arbitrarily small. A five-millisecond timeout on a network with 100 milliseconds of latency would freeze Raft, while in QuePaxa it only increases the number of active proposers. In exchange, hedging is not free: more proposers means more proposals being broadcast, which uses more bandwidth and can take longer to commit. Cloudflare is willing to accept this trade-off.
The four phases in each QuePaxa round
QuePaxa runs in rounds, each consisting of four phases. At the start of each phase, a proposer broadcasts its currently accepted proposal to all recorders, and when it receives replies from a majority of recorders it moves on to the next phase. If the proposal has not been committed by the final phase, a new round begins.
Phase 1 (Spread): the proposer spreads its accepted proposal to a majority of recorders, and the recorders remember the proposal with the highest priority. This step prevents the protocol from later committing a lower-priority proposal. Phase 2 (Check and Decide): the proposer asks a majority of recorders for the highest-priority proposal they saw in the previous phase; if it matches the proposal it is currently accepting, it commits. Phase 3 (Carry Forward): a proposer that has not been able to commit prepares for the next round by accepting the best proposal found at a majority of recorders.


