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 language | English (US) |
---|---|
Pages | 138-147 |
Number of pages | 10 |
DOIs | |
State | Published - 2005 |
Externally published | Yes |
Event | 24th Annual ACM Symposium on Principles of Distributed Computing, PODC 2005 - Las Vegas, NV, United States Duration: Jul 17 2005 → Jul 20 2005 |
Other
Other | 24th Annual ACM Symposium on Principles of Distributed Computing, PODC 2005 |
---|---|
Country/Territory | United States |
City | Las Vegas, NV |
Period | 7/17/05 → 7/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