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 in an infinite grid (or finite toroidal) wireless network. With a forwarding frequency of O(1), our BRB protocol achieves thresholds closer to the thresholds in wired networks. Moreover, we provide the derivations of new thresholds and formally prove the correctness of our BRB protocol.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Byzantine Reliable Broadcast in Wireless Networks

  • Hao Lu,
  • Jian Liu,
  • Kui Ren

摘要

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 in an infinite grid (or finite toroidal) wireless network. With a forwarding frequency of O(1), our BRB protocol achieves thresholds closer to the thresholds in wired networks. Moreover, we provide the derivations of new thresholds and formally prove the correctness of our BRB protocol.