---
_id: '14743'
abstract:
- lang: eng
  text: Leader-based consensus algorithms are fast and efficient under normal conditions,
    but lack robustness to adverse conditions due to their reliance on timeouts for
    liveness. We present QuePaxa, the first protocol offering state-of-the-art normal-case
    efficiency without depending on timeouts. QuePaxa uses a novel randomized asynchronous
    consensus core to tolerate adverse conditions such as denial-of-service (DoS)
    attacks, while a one-round-trip fast path preserves the normal-case efficiency
    of Multi-Paxos or Raft. By allowing simultaneous proposers without destructive
    interference, and using short hedging delays instead of conservative timeouts
    to limit redundant effort, QuePaxa permits rapid recovery after leader failure
    without risking costly view changes due to false timeouts. By treating leader
    choice and hedging delay as a multi-armed-bandit optimization, QuePaxa achieves
    responsiveness to prevalent conditions, and can choose the best leader even if
    the current one has not failed. Experiments with a prototype confirm that QuePaxa
    achieves normal-case LAN and WAN performance of 584k and 250k cmd/sec in throughput,
    respectively, comparable to Multi-Paxos. Under conditions such as DoS attacks,
    misconfigurations, or slow leaders that severely impact existing protocols, we
    find that QuePaxa remains live with median latency under 380ms in WAN experiments.
acknowledgement: The authors would like to thank Marcos K. Aguilera, Pierluca Borsò,
  Aleksey Charapko, Rachid Guerraoui, Jovan Komatovic, Derek Leung, Louis-Henri Merino,
  Shailesh Mishra, Haochen Pan, Rodrigo Rodrigues, Lewis Tseng, and Haoqian Zhang
  for their helpful feedback on early drafts of this paper.
article_processing_charge: No
author:
- first_name: Pasindu
  full_name: Tennage, Pasindu
  last_name: Tennage
- first_name: Cristina
  full_name: Basescu, Cristina
  last_name: Basescu
- first_name: Eleftherios
  full_name: Kokoris Kogias, Eleftherios
  id: f5983044-d7ef-11ea-ac6d-fd1430a26d30
  last_name: Kokoris Kogias
- first_name: Ewa
  full_name: Syta, Ewa
  last_name: Syta
- first_name: Philipp
  full_name: Jovanovic, Philipp
  last_name: Jovanovic
- first_name: Vero
  full_name: Estrada-Galinanes, Vero
  last_name: Estrada-Galinanes
- first_name: Bryan
  full_name: Ford, Bryan
  last_name: Ford
citation:
  ama: 'Tennage P, Basescu C, Kokoris Kogias E, et al. QuePaxa: Escaping the tyranny
    of timeouts in consensus. In: <i>Proceedings of the 29th Symposium on Operating
    Systems Principles</i>. Association for Computing Machinery; 2023:281-297. doi:<a
    href="https://doi.org/10.1145/3600006.3613150">10.1145/3600006.3613150</a>'
  apa: 'Tennage, P., Basescu, C., Kokoris Kogias, E., Syta, E., Jovanovic, P., Estrada-Galinanes,
    V., &#38; Ford, B. (2023). QuePaxa: Escaping the tyranny of timeouts in consensus.
    In <i>Proceedings of the 29th Symposium on Operating Systems Principles</i> (pp.
    281–297). Koblenz, Germany: Association for Computing Machinery. <a href="https://doi.org/10.1145/3600006.3613150">https://doi.org/10.1145/3600006.3613150</a>'
  chicago: 'Tennage, Pasindu, Cristina Basescu, Eleftherios Kokoris Kogias, Ewa Syta,
    Philipp Jovanovic, Vero Estrada-Galinanes, and Bryan Ford. “QuePaxa: Escaping
    the Tyranny of Timeouts in Consensus.” In <i>Proceedings of the 29th Symposium
    on Operating Systems Principles</i>, 281–97. Association for Computing Machinery,
    2023. <a href="https://doi.org/10.1145/3600006.3613150">https://doi.org/10.1145/3600006.3613150</a>.'
  ieee: 'P. Tennage <i>et al.</i>, “QuePaxa: Escaping the tyranny of timeouts in consensus,”
    in <i>Proceedings of the 29th Symposium on Operating Systems Principles</i>, Koblenz,
    Germany, 2023, pp. 281–297.'
  ista: 'Tennage P, Basescu C, Kokoris Kogias E, Syta E, Jovanovic P, Estrada-Galinanes
    V, Ford B. 2023. QuePaxa: Escaping the tyranny of timeouts in consensus. Proceedings
    of the 29th Symposium on Operating Systems Principles. SOSP: Symposium on Operating
    Systems Principles, 281–297.'
  mla: 'Tennage, Pasindu, et al. “QuePaxa: Escaping the Tyranny of Timeouts in Consensus.”
    <i>Proceedings of the 29th Symposium on Operating Systems Principles</i>, Association
    for Computing Machinery, 2023, pp. 281–97, doi:<a href="https://doi.org/10.1145/3600006.3613150">10.1145/3600006.3613150</a>.'
  short: P. Tennage, C. Basescu, E. Kokoris Kogias, E. Syta, P. Jovanovic, V. Estrada-Galinanes,
    B. Ford, in:, Proceedings of the 29th Symposium on Operating Systems Principles,
    Association for Computing Machinery, 2023, pp. 281–297.
conference:
  end_date: 2023-10-26
  location: Koblenz, Germany
  name: 'SOSP: Symposium on Operating Systems Principles'
  start_date: 2023-10-23
date_created: 2024-01-08T12:54:35Z
date_published: 2023-10-01T00:00:00Z
date_updated: 2024-02-28T12:51:24Z
day: '01'
department:
- _id: ElKo
doi: 10.1145/3600006.3613150
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.1145/3600006.3613150
month: '10'
oa: 1
oa_version: Published Version
page: 281-297
publication: Proceedings of the 29th Symposium on Operating Systems Principles
publication_identifier:
  isbn:
  - '9798400702297'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'QuePaxa: Escaping the tyranny of timeouts in consensus'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...