Applying article 10.1's eight-part framework to the paper this entire series was designed to build toward. QuePaxa — Tennage, Basescu, Kokoris-Kogias, Syta, Jovanovic, Estrada-Galiñanes, and Ford, published at SOSP 2023 — targets a specific weakness every classical algorithm since Phase 5 has quietly carried: leader-based consensus depends on timeouts for liveness, and timeouts are a genuinely bad way to detect failure (article 2.4's whole point, revisited here at the level of an actual production-motivated fix rather than a theoretical caveat). QuePaxa's answer is a randomized asynchronous consensus core wrapped around a familiar one-round-trip fast path — matching Multi-Paxos's throughput when conditions are good, and staying live and fast under exactly the adversarial conditions (DoS attacks, WAN jitter, a slow-but-not-dead leader) that make fixed timeouts either too trigger-happy or too sluggish.
1-2. Problem, and why existing algorithms fail
Recall article 4.2's split-vote discussion and article 2.4's phi-accrual detection material: every algorithm since Phase 5 detects a dead leader using a timeout — if no heartbeat arrives within some fixed or randomized window, assume the leader is gone and start an election. QuePaxa's paper names precisely why this is a structural weakness, not just an implementation detail: pick the timeout too short, and ordinary WAN jitter or a momentarily-slow-but-alive leader triggers unnecessary elections, each one costing a full round of coordination and briefly interrupting availability (article 4.1's liveness cost, made concrete and recurring). Pick the timeout too long, and a genuinely failed leader isn't detected — and therefore isn't replaced — for that entire duration, directly hurting availability in the failure case the timeout exists to handle. Worse, an adversary who can selectively delay messages (a realistic threat model for anything reachable over the public internet, and directly relevant to Cloudflare's own motivation for Meerkat, article 10.3 next) can deliberately induce exactly the timing conditions that cause repeated, wasteful re-elections — a denial-of-service vector built directly into the liveness mechanism of Raft and Multi-Paxos as this series has presented them.
3. Core idea: a randomized asynchronous core under a familiar fast path
QuePaxa's structural answer, and the part worth sitting with carefully: it doesn't discard the fast, familiar leader-based path this series has built since article 5.3 — it keeps a one-round-trip fast path that, under normal conditions, performs identically to Multi-Paxos or Raft. What's new sits underneath, as a fallback core: a randomized asynchronous consensus core, directly in the lineage of article 2.5's randomization escape hatch and article 7.8's Rabia (the other randomization-based simplification this series has covered), that allows simultaneous proposers without destructive interference — competing proposals don't have to eliminate each other the way article 5.2's dueling-proposers scenario described; the core's design lets progress continue even when more than one node is actively trying to lead at once.
Hedging delays instead of timeouts, and the multi-armed-bandit angle
The specific mechanism that replaces the timeout: rather than waiting a fixed or randomized-but-blind duration before assuming a leader is dead, QuePaxa uses short hedging delays — a much smaller, adaptively-tuned wait before a backup attempt is launched, sized to limit redundant work rather than to declare failure. Because simultaneous proposers don't destructively interfere (the core idea above), a hedging attempt that turns out to be unnecessary (the original leader was fine) doesn't cost the same disruption a false-positive timeout-triggered election would in Raft. QuePaxa's paper further frames leader selection and hedging-delay tuning as a multi-armed-bandit optimization problem — the system continuously, adaptively learns which node tends to be the fastest, most reliable leader under current conditions and which hedging delay minimizes wasted effort, rather than relying on a single fixed configuration value chosen once at deployment time and never revisited. This lets QuePaxa select a better leader even when the current one hasn't technically failed, purely because conditions have shifted — a genuinely different liveness philosophy from anything in Phase 5 through Phase 7's leader-election material.
Fig 1 — Normal conditions never touch the fallback core at all; it only activates when the fast path's assumptions are actually violated.
4-6. Architecture, failure handling, and performance, together
QuePaxa's evaluation reports normal-case throughput of roughly 584,000 commands per second in a LAN setting and roughly 250,000 commands per second over WAN — figures the paper positions as comparable to Multi-Paxos, directly supporting the claim that the fast path genuinely doesn't sacrifice normal-case performance for its adversarial robustness. The more interesting numbers are under adverse conditions specifically: the paper reports roughly a 10x throughput improvement over Raft and Multi-Paxos under adversarial network conditions designed to trigger exactly the false-timeout pathology described above, with WAN median latency staying under 380 milliseconds even during simulated DoS attacks, misconfigurations, and deliberately slow-but-alive leaders — conditions under which timeout-based algorithms this series covered in Phase 5 are shown, in the paper's own experiments, to degrade far more sharply.
| Condition | Raft/Multi-Paxos (Phase 5) | QuePaxa |
|---|---|---|
| Normal LAN/WAN operation | Baseline, fast | Comparable (~584k/250k cmd/s) — no normal-case penalty |
| Adversarial conditions (DoS, jitter, slow leader) | Sharp degradation — repeated false-timeout elections | ~10x higher throughput; WAN median latency under 380ms |
| Liveness mechanism | Fixed/randomized timeout | Hedging delays + randomized async core, no timeout-triggered elections |
7. Trade-offs, stated honestly
Consistent with this series' insistence, since Phase 7, on never presenting a variant as a free upgrade: QuePaxa's fallback core, and the multi-armed-bandit tuning layered on top of it, are genuinely more complex than Raft's comparatively simple timeout-and-reelect logic — exactly the kind of added mechanism complexity article 8.6's Jepsen coverage flagged as fertile ground for subtle implementation bugs, a risk that applies with particular force to a mechanism this new and this recently published. The benefit is concentrated specifically in adversarial or high-jitter WAN conditions; for a small, stable, low-jitter, single-datacenter deployment where timeouts rarely misfire in practice, Raft's simpler mechanism may remain the more pragmatic choice, precisely the same "match the tool to the actual conditions" argument article 9.5's WAN-optimization material made for read techniques.
Project history: from QSCOD and Raxos to QuePaxa
Worth knowing for anyone tracing this work further: the project's public GitHub repository notes the codebase was previously developed under the names Raxos and QSCOD before settling on QuePaxa for the SOSP 2023 publication — a reminder, consistent with this whole series' repeated observation about naming and presentation mattering (article 5.1's Paxos allegory story, article 5.7's Zab/epoch naming), that a research project's public name is often the last thing to stabilize, well after its core technical contribution has been worked out. The authors are affiliated with EPFL's DEDIS lab (Decentralized and Distributed Systems), a research group whose broader body of work spans several adjacent areas this series has touched — Byzantine fault tolerance, randomized consensus, and decentralized systems more generally — placing QuePaxa within a specific, traceable research lineage rather than as an isolated one-off contribution.
Why multi-armed bandits specifically, not just "adaptive tuning"
It's worth being precise about why the paper frames leader and hedging-delay selection using multi-armed-bandit terminology specifically, rather than simply saying "adaptive." A multi-armed bandit is the classical formalization of a decision-maker repeatedly choosing among several options ("arms") with unknown, potentially-changing payoffs, needing to balance exploration (trying options that might be better but are currently uncertain) against exploitation (sticking with the option currently believed best). Applied to QuePaxa's leader selection: each candidate node is an "arm," its recent latency and success rate are its observed "payoff," and the system needs to continuously balance sticking with a currently-good leader against occasionally testing whether a different node has become faster or more reliable as conditions shift — exactly the exploration/exploitation trade-off multi-armed bandit algorithms are designed to formalize and solve well. This is a genuinely more principled foundation than an ad-hoc heuristic (like "switch leaders if latency exceeds some fixed threshold N times in a row"), because it comes with its own established theoretical guarantees about how quickly and how reliably the system converges on a good choice.
FAQ
Does QuePaxa still rely on the same majority-overlap safety mechanism as Phase 5's algorithms?
Yes — QuePaxa's safety guarantee still rests on majority quorums and the overlap argument article 3.3 built from first principles; what QuePaxa changes is exclusively the liveness mechanism (how a leader is chosen and replaced), not the underlying safety proof, consistent with this entire series' repeated finding that safety and liveness (article 4.1) are addressed by largely separable mechanisms.
Is QuePaxa a leaderless algorithm like EPaxos (7.1)?
Not quite the same shape — QuePaxa retains a fast path that behaves like a conventional single-leader protocol under good conditions, unlike EPaxos's fully leaderless, dependency-graph-based design. QuePaxa's novelty is in how it handles the transition away from a leader when conditions are adverse, not in removing the leader concept from the normal-case path entirely.
Why does the 10x throughput improvement only show up under adversarial conditions?
Because that's precisely the condition QuePaxa targets — under good conditions, both QuePaxa and Raft/Multi-Paxos operate near their shared fast-path ceiling, so there's little room for one to meaningfully outperform the other. The 10x gap appears specifically because Raft/Multi-Paxos's timeout-based liveness mechanism degrades sharply under adversarial jitter, while QuePaxa's hedging-delay-based mechanism was purpose-built not to.
Takeaways
- QuePaxa (Tennage, Basescu, Kokoris-Kogias, Syta, Jovanovic, Estrada-Galiñanes & Ford, SOSP 2023) targets the structural weakness every Phase 5 algorithm carries: timeout-based liveness is either too trigger-happy or too sluggish, and is a built-in denial-of-service vector.
- A familiar one-round-trip fast path matches Multi-Paxos/Raft throughput under normal conditions — the innovation is entirely in the fallback mechanism.
- A randomized asynchronous core allows simultaneous proposers without destructive interference, replacing timeout-triggered elections with adaptive hedging delays.
- Leader and hedging-delay selection is framed as a multi-armed-bandit optimization, letting the system adapt continuously rather than relying on one fixed configuration.
- Reported results: comparable normal-case throughput to Multi-Paxos, roughly 10x higher throughput under adversarial conditions, WAN median latency under 380ms during simulated DoS/jitter/slow-leader scenarios.
- The honest cost: genuinely more implementation complexity than Raft's simpler mechanism, a benefit concentrated specifically in adversarial or high-jitter WAN deployments.
References & further reading
- Tennage, Basescu, Kokoris-Kogias, Syta, Jovanovic, Estrada-Galiñanes & Ford — QuePaxa: Escaping the Tyranny of Timeouts in Consensus (SOSP 2023) — the primary source.
- ACM Digital Library — QuePaxa (SOSP 2023 proceedings) — the official publication record.
- DEDIS Lab — QuePaxa reference implementation — the project's own code repository (formerly named Raxos/QSCOD).
- cvam.sight — Consensus 2.4: Failure Models and Failure Detectors — the timeout-based detection foundation QuePaxa moves beyond.