2026-09-22T03:10:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22567 2026-09-05T17:49:24Z ddc:004 open_access

Dynamic Probabilistic Reliable Broadcast Bezerra, João Paulo Anikina, Veronika Kuznetsov, Petr Schiff, Liron Schmid, Stefan Reliable broadcast probabilistic algorithms witness sets stream-local hashing cryptocurrencies accountability Byzantine reliable broadcast is a fundamental primitive in distributed systems that allows a set of processes to agree on a message broadcast by a dedicated process, even when some of them are malicious (Byzantine). It guarantees that no two correct processes deliver different messages, and if a message is delivered by a correct process, every correct process eventually delivers one. Byzantine reliable broadcast protocols are known to scale poorly, as they require Ω(n²) message exchanges, where n is the number of system members. The quadratic cost can be explained by the inherent need for every process to relay a message to every other process. In this paper, we explore ways to overcome this limitation by casting the problem to the probabilistic setting. We propose a solution in which every broadcast message is validated by a small set of witnesses, which allows us to maintain low latency and small communication complexity. In order to tolerate the slow adaptive adversary, we dynamically select the witnesses through a novel stream-local hash function: given a stream of inputs, it generates a stream of output hashed values that adapts to small deviations of the inputs. Our performance analysis shows that the proposed solution exhibits significant scalability gains over state-of-the-art protocols. Schloss Dagstuhl – Leibniz-Zentrum für Informatik João Paulo Bezerra and Veronika Anikina and Petr Kuznetsov and Liron Schiff and Stefan Schmid 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.31 urn:nbn:de:0030-drops-225679 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.31 eng https://creativecommons.org/licenses/by/4.0/legalcode