Cloudflare Engineers Explain: Why Raft Stalls on the Global Internet, and How QuePaxa Bypasses Fault Detection with Optional Leaders
Cloudflare’s Meerkat global consensus service selected the QuePaxa algorithm, published in 2023, over Raft or Paxos. The three authors explain that leader-based consensus suffers from systematic stalls in wide-area networks due to false fault detection and destructive interference during elections; QuePaxa achieves continuous request processing even when leaders fail through three design choices—optional leaders, constructive interference, and hedging timeouts unconstrained by network latency—reducing decision rates to a minimum of 65% rather than zero.
The default choice for distributed consensus systems is Raft or Paxos; they are mature, understandable, and work well in local area networks. However, Cloudflare’s Meerkat service needs to operate across continents, where connection links often exhibit high and volatile latency. The three authors, João Pedro Leite, Bob Halley, and James Larisch, explain that this environment led them to abandon all mainstream algorithms in favor of QuePaxa, published in 2023 by Tennage, Băsescu, et al.
The root of the problem lies in two structural flaws of leader-based consensus. The first is destructive interference: when a leader fails or slows down, multiple replicas simultaneously initiate elections, blocking each other from obtaining a majority vote, causing elections to repeatedly fail. Even if a network fault lasts only two seconds, an election storm can persist far longer than the fault itself. The authors term this metastable failure—a failure pattern that sustains itself even after the initial cause has disappeared.
The second flaw is fault detection itself. In asynchronous networks, a process cannot directly observe whether a remote process is dead; it can only observe whether expected messages arrive on time. Latency spikes and connection interruptions make healthy leaders appear failed. Raft typically deploys an election timeout at five to ten times the network round-trip time; on transoceanic links with round-trip times in the hundreds of milliseconds, detecting a failed coordinator may take nearly a second—during which time the system is completely stalled. Cloudflare experienced this firsthand in 2020: a partial failure of a core network switch caused an internal consensus system to degrade, slowing dashboard operations to one-eightieth of normal speed for six hours. No data was lost, but writes were entirely unavailable.