2026-08-04T08:57:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22552 2025-10-02T11:06:02Z ddc:004 open_access

Byzantine Reliable Broadcast with Low Communication and Time Complexity Locher, Thomas Asynchronous Networks Reliable Broadcast Communication Complexity Byzantine reliable broadcast is a fundamental problem in distributed computing, which has been studied extensively over the past decades. State-of-the-art algorithms are predominantly based on the approach to share encoded fragments of the broadcast message, yielding an asymptotically optimal communication complexity when the message size exceeds the network size, a condition frequently encountered in practice. However, algorithms following the standard coding approach incur an overhead factor of at least 3, which can already be a burden for bandwidth-constrained applications. Minimizing this overhead is an important objective with immediate benefits to protocols that use a reliable broadcast routine as a building block. This paper introduces a novel mechanism to lower the communication and computational complexity. Two algorithms are presented that employ this mechanism to reliably broadcast messages in an asynchronous network where less than a third of all nodes are Byzantine. The first algorithm reduces the overhead factor to 2 and has a time complexity of 3 if the sender is honest, whereas the second algorithm attains an optimal time complexity of 2 with the same overhead factor in the absence of equivocation. Moreover, an optimization is proposed that reduces the overhead factor to 3/2 under normal operation in practice. Lastly, a lower bound is proved that an overhead factor lower than 3/2 cannot be achieved for a relevant class of reliable broadcast algorithms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Locher 2025 Is Part Of LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2024.16 urn:nbn:de:0030-drops-225524 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.16 eng https://creativecommons.org/licenses/by/4.0/legalcode