skip to main content
10.1145/1146381.1146420acmconferencesArticle/Chapter ViewAbstractPublication PagespodcConference Proceedingsconference-collections
Article

Reliable broadcast in radio networks: the bounded collision case

Published: 23 July 2006 Publication History

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.

References

[1]
P. Berman and J. A. Garay. Asymptotically optimal distributed consensus (extended abstract). ICALP '89.]]
[2]
V. Bhandari and N. H. Vaidya. On reliable broadcast in a radio network. PODC 2005.]]
[3]
V. Bhandari and N. H. Vaidya. On reliable broadcast in a radio network: A simplified characterization. Technical Report, CSL, UIUC, May 2005. Available at http://www.crhc.uiuc.edu/wireless/papers/bcast-addendum.pdf]]
[4]
V. Bhandari and N. H. Vaidya. Reliable broadcast in a wireless grid network with probabilistic failures. Technical Report, CSL, UIUC, Oct. 2005 (A revised version is under preparation).]]
[5]
G. Chockler, M. Demirbas, S. Gilbert, C. Newport, and T. Nolte. Consensus and collision detectors in wireless ad hoc networks. PODC 2005.]]
[6]
J. Considine, M. Fitzi, M. Franklin, L.A. Levin, U. Maurer, and D. Metcalf. Byzantine agreement given partial broadcast. J. Cryptology 18(3): 191--217, 2005.]]
[7]
S. Gilbert, R. Guerraoui, and C. Newport. Of malicious motes and suspicious sensors. Technical Report MIT-CSAIL-TR-2006-026, CSAIL, Massachusetts Institute of Technology, April 2006.]]
[8]
C.-Y. Koo. Broadcast in radio networks tolerating Byzantine adversarial behavior. PODC 2004.]]
[9]
E. Kranakis, D. Krizanc, and A. Pelc. Fault-tolerant broadcasting in radio networks. J. Algorithms 39(1): 47--67, 2001.]]
[10]
E. Kreyszig. Advanced Engineering Mathematics, 7th edition. John Wiley & Sons, 1993.]]
[11]
M. Pease, R. Shostak, and L. Lamport. Reaching agreement in the presence of faults. J. ACM 27(2): 228--234, 1980.]]
[12]
A. Pelc and D. Peleg. Broadcasting with locally bounded Byzantine faults. Information Processing Letters 93(3): 109--115, 2005.]]
[13]
A. Pelc and D. Peleg. Feasibility and complexity of broadcasting with random transmission failures. PODC 2005.]]
[14]
V. Vaikuntanathan. Brief announcement: broadcast in radio networks in the presence of Byzantine adversaries. PODC 2005.]]

Cited By

View all
  • (2022)Resilient Trajectory Propagation in Multirobot NetworksIEEE Transactions on Robotics10.1109/TRO.2021.312707638:1(42-56)Online publication date: Feb-2022
  • (2022)Byzantine Fault-Tolerant Causal Broadcast on Incomplete Graphs2022 IEEE 21st International Symposium on Network Computing and Applications (NCA)10.1109/NCA57778.2022.10013642(63-71)Online publication date: 14-Dec-2022
  • (2019)Exact Byzantine Consensus on Undirected Graphs under Local Broadcast ModelProceedings of the 2019 ACM Symposium on Principles of Distributed Computing10.1145/3293611.3331619(327-336)Online publication date: 16-Jul-2019
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing
July 2006
230 pages
ISBN:1595933840
DOI:10.1145/1146381
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 July 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. broadcast
  2. byzantine failure
  3. fault tolerance
  4. radio networks

Qualifiers

  • Article

Conference

PODC06

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)4
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2022)Resilient Trajectory Propagation in Multirobot NetworksIEEE Transactions on Robotics10.1109/TRO.2021.312707638:1(42-56)Online publication date: Feb-2022
  • (2022)Byzantine Fault-Tolerant Causal Broadcast on Incomplete Graphs2022 IEEE 21st International Symposium on Network Computing and Applications (NCA)10.1109/NCA57778.2022.10013642(63-71)Online publication date: 14-Dec-2022
  • (2019)Exact Byzantine Consensus on Undirected Graphs under Local Broadcast ModelProceedings of the 2019 ACM Symposium on Principles of Distributed Computing10.1145/3293611.3331619(327-336)Online publication date: 16-Jul-2019
  • (2019)Resilient Leader-Follower Consensus to Arbitrary Reference Values in Time-Varying GraphsIEEE Transactions on Automatic Control10.1109/TAC.2019.2934954(1-1)Online publication date: 2019
  • (2019)Resilient Leader-Follower Consensus with Time-Varying Leaders in Discrete-Time Systems2019 IEEE 58th Conference on Decision and Control (CDC)10.1109/CDC40024.2019.9030246(5432-5437)Online publication date: Dec-2019
  • (2018)A resource-competitive jamming defenseDistributed Computing10.1007/s00446-017-0313-331:6(419-439)Online publication date: 1-Nov-2018
  • (2018)SadeDistributed Computing10.1007/s00446-017-0307-131:3(241-254)Online publication date: 1-Jun-2018
  • (2014)Principles of Robust Medium Access and an Application to Leader ElectionACM Transactions on Algorithms10.1145/263581810:4(1-26)Online publication date: 13-Aug-2014
  • (2014)(Near) optimal resource-competitive broadcast with jammingProceedings of the 26th ACM symposium on Parallelism in algorithms and architectures10.1145/2612669.2612679(257-266)Online publication date: 23-Jun-2014
  • (2014)The Byzantine Generals Problem in Generic and Wireless NetworksApplications of Mathematics and Informatics in Science and Engineering10.1007/978-3-319-04720-1_25(405-415)Online publication date: 29-Mar-2014
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media