Paper Info
Title
Balanced Byzantine Reliable Broadcast with Near-Optimal Communication and Improved Computation
Abstract
BSTRACTThis paper studies Byzantine reliable broadcast (BRB) under asynchronous networks, and improves the state-of-the-art protocols from the following aspects. Near-optimal communication cost: We propose two new BRB protocols for n nodes and input message M that has communication cost O(n|M|+n2 logn), which is nearoptimal due to the lower bound of Ω(n|M|+n2). The first RBC protocol assumes threshold signature but is easy to understand, while the second RBC protocol is error-free but less intuitive. Improved computation:We propose a newconstruction that improves the computation cost of the state-of-the-art BRB by avoiding the expensive online error correction on the input message, while achieving the same communication cost. Balanced communication: We propose a technique named balanced multicast that can balance the communication cost for BRB protocols where the broadcaster needs to multicast the message M while other nodes only needs to multicast coded fragments of size O(|M|/n + logn). The balanced multicast technique can be applied to many existing BRB protocols as well as all our new constructions in this paper, and can make every node incur about the same communication cost. Finally, we present a lower bound to show the near optimality of our protocol in terms of communication cost at each node.
Year
DOI
Venue
2022
10.1145/3519270.3538475
Principles of Distributed Computing
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
0
7
Name
Order
Citations
PageRank
Nicolas Alhaddad111.03
Sourav Das221.73
Sisi Duan300.68
Ling Ren401.01
Mayank Varia500.68
Zhuolun Xiang601.01
Haibin Zhang711818.58