Paper 2024/2017

Byzantine Reliable Broadcast in Wireless Networks

Abstract

Byzantine reliable broadcast (BRB) is a fundamental primitive in distributed computing. BRB ensures that messages can be reliably broadcast among nodes, regardless of the presence of Byzantine nodes. Research on BRB in wireless networks receives relatively less attention, while there have been significant advancements in wired networks. Although current works have yielded remarkable results, they still have some limitations. Specifically, the forwarding frequency of each node is $O(n)$, and the fault-tolerant thresholds still have a gap with the thresholds in wired networks where less than one-third of nodes can be faulty. In this paper, we propose a new BRB protocol that outperforms the state-of-the-art (SOTA) presented in PODC '05 in the following three respects: - It improves the threshold in the $L_\infty$ metric from $f < \frac{1}{2}r(2r+1)$ to $f < \lfloor \frac{1}{2}(r+1)(2r+1) \rfloor$. - It improves the threshold in the $L_2$ metric from $f < 0.23 \pi r^2$ to $f < \lfloor 0.3\pi r^2 \rfloor$. - It reduces the forwarding frequency from $O(n)$ to $O(1)$. In summary, our BRB has a constant forwarding frequency and achieves thresholds closer to the thresholds in wired networks. We provide the derivations of new thresholds and formally prove the correctness of our BRB protocol.