Broadcast in radio networks tolerating byzantine adversarial behavior
Author:
Open Access
- 25 July 2004
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 275-282
Abstract
Much work has focused on the Byzantine Generals (or secure broadcast) problem in the standard model in which pairwise communication is available between all parties in the network. Some research has also explored the problem when pairwise channels exist only between selected pairs of players, or under the assumption of "k-cast channels" shared by all subsets of players of size k. However, none of these models are appropriate for radio networks in which a player can communicate only by multicasting a message which is then received by all players within some radius r (i.e., the neighbors of the transmitting node). Yet, as far as we are aware, obtaining secure broadcast in radio networks in the presence of a Byzantine adversary has not been studied before.This paper corrects this omission, and provides the first analysis of secure broadcast in radio networks for the case of Byzantine adversaries. We note that secure broadcast is impossible in the presence of an omnipotent adversary. To bypass this barrier, we make the following assumption: there exists a prefixed schedule for players to communicate and everyone (including corrupted ones) adheres to this schedule. Under this assumption, we give a simple broadcast protocol which is provably secure whenever the adversary corrupts at most 14 r(r+√rover2 + 1)-3 neighbors (roughly a 1/4π fraction) of any honest player. On the other hand, we show that it is impossible to achieve secure broadcast when the adversary corrupts ⌈1/2 r(2r+1)⌉ (roughly a 1/π fraction) neighbors of any honest player.Keywords
This publication has 9 references indexed in Scilit:
- Distributed consensus in the presence of sectional faults2003
- Broadcasting in undirected ad hoc radio networks2003
- From partial consistency to global broadcast2000
- Fault-Tolerant Broadcasting in Radio Networks (Extended Abstract)Lecture Notes in Computer Science, 1998
- Reliable broadcast in mobile multihop packet networks1997
- An Ω(D log(N/D)) lower bound for broadcast in radio networks1993
- A lower bound for radio broadcastJournal of Computer and System Sciences, 1991
- The Byzantine Generals ProblemACM Transactions on Programming Languages and Systems, 1982
- Reaching Agreement in the Presence of FaultsJournal of the ACM, 1980