Reliable broadcast in radio networks: The bounded collision case

Chiu Yuen Koo, Jonathan Katz, Vartika Bhandari, Nitin H. Vaidya

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 25th Annual ACM Symposium on Principles of Distributed Computing 2006
Pages258-264
Number of pages7
StatePublished - Sep 21 2006
Event25th Annual ACM Symposium on Principles of Distributed Computing 2006 - Denver, CO, United States
Duration: Jul 23 2006Jul 26 2006

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing
Volume2006

Other

Other25th Annual ACM Symposium on Principles of Distributed Computing 2006
CountryUnited States
CityDenver, CO
Period7/23/067/26/06

Keywords

  • Broadcast
  • Byzantine failure
  • Fault tolerance
  • Radio networks

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this

Koo, C. Y., Katz, J., Bhandari, V., & Vaidya, N. H. (2006). Reliable broadcast in radio networks: The bounded collision case. In Proceedings of the 25th Annual ACM Symposium on Principles of Distributed Computing 2006 (pp. 258-264). (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing; Vol. 2006).