2023/06/07 by V.G. Anikina, João Paulo Peres Bezerra, Anikina, Veronika +7
Computer Science · Engineering · #Cryptography and Data Security #Distributed #FOS: Computer and information sciences #Parallel #Privacy-Preserving Technologies in Data #Wireless Communication Security Techniques #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2306.04221
openalex publication_date 2023/06/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Ω(n2) 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.