On reliable broadcast in a radio network

Vartika Bhandari, Nitin H. Vaidya

Research output: Contribution to conferencePaperpeer-review

Abstract

We consider the problem of reliable broadcast in an infinite grid (or finite toroidal) radio network under Byzantine and crash-stop failures. We present bounds on the maximum number of failures that may occur in any given neighborhood without rendering reliable broadcast impossible, We improve on previously proved bounds for the number of tolerable Byzantine faults [6]. Our results indicate that it is possible to achieve reliable broadcast if slightly less than one-fourth fraction of nodes in any neighborhood are faulty, and impossible otherwise. We also show that reliable broadcast is achievable with crash-stop failures if slightly less than half the nodes in any given neighborhood may be faulty. In particular, we establish exact thresholds under a specific distance metric.

Original languageEnglish (US)
Pages138-147
Number of pages10
DOIs
StatePublished - Dec 1 2005
Event24th Annual ACM Symposium on Principles of Distributed Computing, PODC 2005 - Las Vegas, NV, United States
Duration: Jul 17 2005Jul 20 2005

Other

Other24th Annual ACM Symposium on Principles of Distributed Computing, PODC 2005
Country/TerritoryUnited States
CityLas Vegas, NV
Period7/17/057/20/05

Keywords

  • Broadcast
  • Byzantine failure
  • Crash-stop failure
  • Fault Tolerance
  • Radio Network

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this