Title | ||
---|---|---|
Message-Efficient Byzantine Fault-Tolerant Broadcast in a Multi-hop Wireless Sensor Network |
Abstract | ||
---|---|---|
We consider message-efficient broadcast tolerating Byzantine faults in a multi-hop wireless sensor network. Assuming a grid network where all nodes have a communication range of $r$, and a single neighborhood contains at most $t$ dishonest and collision-capable (bad) nodes, each with a message budget $m_f$, we investigate the minimum message budget $m$ that each honest (good) node must have in order to achieve reliable broadcast. We consider three cases: (1) $m_f$ is known in advance and $m$ is homogeneous among all good nodes, (2) $m_f$ is known in advance and $m$ is heterogeneous among good nodes, (3) $m_f$ is unknown. For the first two cases, we present possibility results and broadcast protocols that have message costs within twice the lower bound. For the third case, we present a coding scheme that helps verify the integrity of messages at a receiving node without using any cryptographic techniques. This code leads to a {\em reactive local broadcast} primitive that has probabilistic reliability guarantees. Combined with a previously proposed scheme, it results in a broadcast protocol for $t |
Year | DOI | Venue |
---|---|---|
2010 | 10.1109/ICDCS.2010.30 | ICDCS |
Keywords | Field | DocType |
coding scheme,message budget,byzantine fault-tolerant broadcast,multi-hop wireless sensor network,message cost,minimum message budget,reliable broadcast,em reactive local broadcast,message-efficient broadcast,grid network,good node,broadcast protocol,fault tolerant,wireless sensor networks,sensor network,cryptographic protocols,broadcast,cryptography,protocols,byzantine,base stations,lower bound,broadcasting,distributed computing,spread spectrum communication,fault tolerance,wireless sensor network | Broadcasting,Base station,Atomic broadcast,Cryptographic protocol,Computer science,Grid network,Cryptography,Byzantine fault tolerance,Computer network,Wireless sensor network,Distributed computing | Conference |
ISSN | Citations | PageRank |
1063-6927 | 8 | 0.42 |
References | Authors | |
11 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Marin Bertier | 1 | 382 | 24.31 |
Anne-Marie Kermarrec | 2 | 6649 | 453.63 |
Guang Tan | 3 | 373 | 26.97 |