Reliable broadcast in radio networks: the bounded collision case

TitleReliable broadcast in radio networks: the bounded collision case
Publication TypeConference Papers
Year of Publication2006
AuthorsKoo C-Y, Bhandari V, Katz J, Vaidya NH
Conference NameProceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing
Date Published2006///
Conference LocationNew York, NY, USA
ISBN Number1-59593-384-0
Keywordsbroadcast, byzantine failure, Fault tolerance, radio networks

We study the problem of achieving global broadcast in a radio network where a node can multicast messages to all of its neighbors (that is, nodes within some given distance r), and up to t nodes in any single neighborhood may be corrupted. Previous work assumes that corrupted nodes can neither cause collisions nor spoof addresses of honest nodes. In this work, we eliminate these assumptions and allow each faulty node to cause a (known) bounded number of collisions and spoof the addresses of arbitrary other nodes. We show that the maximum tolerable t in this case is identical to the maximum tolerable t when collisions and address spoofing are not allowed. Thus, by causing collisions and spoofing addresses an adversary may be able to degrade the efficiency of achieving broadcast, but it cannot affect the feasibility of this task.