Message-Efficient Byzantine Fault-Tolerant Broadcast in a Multi-Hop Wireless Sensor Network

Marin Bertier 1 Anne-Marie Kermarrec 1 Guang Tan 1, *
* Auteur correspondant
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
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 < \frac 1{2} r(2r+1)$ that guarantees reliability with high probability.
Type de document :
Communication dans un congrès
The 30th International Conference on Distributed Computing Systems, Jun 2010, Genoa, Italy. 2010
Liste complète des métadonnées

https://hal.inria.fr/inria-00457215
Contributeur : Guang Tan <>
Soumis le : mardi 16 février 2010 - 17:35:23
Dernière modification le : mardi 16 janvier 2018 - 15:54:13
Document(s) archivé(s) le : vendredi 18 juin 2010 - 18:07:11

Fichier

malisse-icdcs10.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00457215, version 1

Citation

Marin Bertier, Anne-Marie Kermarrec, Guang Tan. Message-Efficient Byzantine Fault-Tolerant Broadcast in a Multi-Hop Wireless Sensor Network. The 30th International Conference on Distributed Computing Systems, Jun 2010, Genoa, Italy. 2010. 〈inria-00457215〉

Partager

Métriques

Consultations de la notice

426

Téléchargements de fichiers

381