2026-07-25T02:34:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17638 2024-03-06T11:00:11Z ddc:004 open_access

Make Every Word Count: Adaptive Byzantine Agreement with Fewer Words Cohen, Shir Keidar, Idit Spiegelman, Alexander Byzantine Agreement Byzantine Broadcast Adaptive communication Byzantine Agreement (BA) is a key component in many distributed systems. While Dolev and Reischuk have proven a long time ago that quadratic communication complexity is necessary for worst-case runs, the question of what can be done in practically common runs with fewer failures remained open. In this paper we present the first Byzantine Broadcast algorithm with O(n(f+1)) communication complexity in a model with resilience of n = 2t+1, where 0 ≤ f ≤ t is the actual number of process failures in a run. And for BA with strong unanimity, we present the first optimal-resilience algorithm that has linear communication complexity in the failure-free case and a quadratic cost otherwise. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shir Cohen and Idit Keidar and Alexander Spiegelman 2023 Is Part Of LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2022.18 urn:nbn:de:0030-drops-176385 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.18 eng https://creativecommons.org/licenses/by/4.0/legalcode