Repeated Agreement is Cheap! On Weak Accountability and Multishot Byzantine Agreement
Byzantine Agreement (BA) allows n processes to propose input values to reach consensus on a common, valid Lo-bit value, even in the presence of up to t < n faulty processes that can deviate arbitrarily from the protocol. Although strategies like randomization, adaptiveness, and batching have been extensively explored to mitigate the inherent limitations of one-shot agreement tasks, there has been limited progress on achieving good amortized performance for multi-shot agreement, despite its obvious relevance to long-lived functionalities such as state machine replication.
Authors
- Manuel Vidigueira (ORCID: https://orcid.org/0009-0008-5821-2571)
- Muhammad Ayaz Dzulfikar (ORCID: https://orcid.org/0009-0002-7962-0677)
- Seth Gilbert (ORCID: https://orcid.org/0000-0003-3298-7412)
- Rachid Guerraoui (ORCID: https://orcid.org/0000-0002-4794-8902)
- Jovan Komatovic (ORCID: https://orcid.org/0009-0006-9714-4079)
- Pierre Civit (ORCID: https://orcid.org/0000-0003-2394-1201)
Institutions
- National University of Singapore (SG)
- École Polytechnique Fédérale de Lausanne (CH)
Publication Details
- Published
- 2025-06-13
- DOI
- https://doi.org/10.1145/3732772.3733520
- Primary Topic
- Cryptography and Data Security
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Ministry of Education - Singapore
- Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung
- Ministry of Education, India