Paper 2026/2952

Beyond Leaderless: Randomized Consensus Against Mobile Crashes

Ittai Abraham, a16z frontier
Kaya Alpturer, Princeton University
Pranav Garimidi, a16z frontier
Joachim Neu, Technion – Israel Institute of Technology
Tim Roughgarden, Institute for Advanced Study, a16z frontier
Ertem Nusret Tas, a16z frontier
Abstract

Many consensus protocols fail to terminate under attack from an adversary that has the power to move between replicas and repeatedly crash one of them, even in synchrony. We present Multi-Leader Fixed-View Simplex (ML-FVS) to defend against such an adversary while keeping the simple structure and good-case latency of Simplex consensus. Our protocol extends fixed-view Simplex with multiple leaders, each of which may broadcast a proposal. At the voting deadline, each replica votes on the set of proposals it has seen so far. A hidden threshold beacon revealed after the votes gives a priority order on the multiple leaders, resolving each vote to its highest-priority proposal. Our model combines permanent adaptive Byzantine faults with mobile crashes. For a constant crash budget and Δ-delayed Byzantine corruption, we obtain O(Δ) expected latency over repeated views whose leaders start honest. With immediate Byzantine corruptions, the protocol still achieves liveness. We also evaluate the protocol under random network delays and stochastic faults, finding that multiple leaders reduce view failures even when rational leaders delay their proposals to increase rewards.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
consensusleaderless
Contact author(s)
iabraham @ a16z com
kalpturer @ princeton edu
pgarimidi @ a16z com
joachimneu @ gmail com
tim roughgarden @ gmail com
ntas @ a16z com
History
2026-11-22: approved
2026-11-19: received
See all versions
Short URL
https://ia.cr/2026/2952
License
Creative Commons Attribution-NonCommercial-NoDerivs
CC BY-NC-ND

BibTeX

@misc{cryptoeprint:2026/2952,
      author = {Ittai Abraham and Kaya Alpturer and Pranav Garimidi and Joachim Neu and Tim Roughgarden and Ertem Nusret Tas},
      title = {Beyond Leaderless: Randomized Consensus Against Mobile Crashes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2952},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2952}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.