Amortized Asynchronous Byzantine Reliable Broadcast with Optimal Resilience
It addresses the open problem of achieving sub-quadratic communication in asynchronous BRB without sacrificing optimal resilience, benefiting distributed systems and cryptographic protocols that require reliable broadcast in asynchronous settings.
This work presents a multi-shot Byzantine Reliable Broadcast (BRB) protocol for asynchronous networks that achieves optimal resilience (f < n/3) and asymptotic optimal O(n|m|) message complexity for large messages, using amortization across rounds. The protocol has Ω(n) worst-case round complexity but can achieve Ω(1) under optimistic conditions.
Byzantine Reliable Broadcast (BRB) is a fundamental primitive in distributed computing and cryptographic systems. Reducing the communication complexity of BRB protocols remains an important research direction. However, most work focuses on synchronous networks, with limited attention to the more challenging setting of network \textit{asynchrony}. Achieving sub-quadratic communication for asynchronous BRB typically requires probabilistic approaches that sacrifice optimal $f=\frac{n}{3}$ resilience. In this work, we present a multi-shot BRB algorithm for asynchronous networks that maintains optimal resilience through an underutilized technique: \textit{amortization}. Our protocol structures BRB across multiple rounds, where each round provides incremental additive guarantees. Once these initial rounds complete, each subsequent BRB instance requires only a single additional round. This amortization strategy achieves asymptotic optimal $O(n|m|)$ message complexity when messages are sufficiently large, with $Ω(n)$ round complexity in the worst case. Under favorable conditions, an optimistic delivery path reduces the round complexity to $Ω(1)$.