Reliable Broadcast in Radio Networks with Locally Bounded Failures

摘要

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.