Reliable Broadcast in radio networks with locally bounded failures

Vartika Bhandari, Nitin H. Vaidya

Research output: Contribution to journalArticlepeer-review

Abstract

This paper studies the reliable broadcast problem in a radio network with locally bounded failures. We present a sufficient condition for achievability of reliable broadcast in a general graph subject to Byzantine/crash-stop failures. We then 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. For the Byzantine failure model, we describe an algorithm which is optimal for the grid network model, as it tolerates faults up to a previously established upper bound for this model. 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. 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.

Original languageEnglish (US)
Article number5010434
Pages (from-to)801-811
Number of pages11
JournalIEEE Transactions on Parallel and Distributed Systems
Volume21
Issue number6
DOIs
StatePublished - 2010

Keywords

  • Broadcast
  • Byzantine failure
  • Crash-stop failure
  • Fault tolerance
  • Radio network.

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Reliable Broadcast in radio networks with locally bounded failures'. Together they form a unique fingerprint.

Cite this