On Byzantine Broadcast in Loosely Connected Networks

Abstract : We consider the problem of reliably broadcasting information in a multihop asynchronous network that is subject to Byzantine failures. Most existing approaches give conditions for perfect reliable broadcast (all correct nodes deliver the authentic message and nothing else), but they require a highly connected network. An approach giving only probabilistic guarantees (correct nodes deliver the authentic message with high probability) was recently proposed for loosely connected networks, such as grids and tori. Yet, the proposed solution requires a specific initialization (that includes global knowledge) of each node, which may be difficult or impossible to guarantee in self-organizing networks - for instance, a wireless sensor network, especially if they are prone to Byzantine failures. In this paper, we propose a new protocol offering guarantees for loosely connected networks that does not require such global knowledge dependent initialization. In more details, we give a methodology to determine whether a set of nodes will always deliver the authentic message, in any execution. Then, we give conditions for perfect reliable broadcast in a torus network. Finally, we provide experimental evaluation for our solution, and determine the number of randomly distributed Byzantine failures than can be tolerated, for a given correct broadcast probability.
Type de document :
Communication dans un congrès
26th International Symposium on Distributed Computing, DISC 2012, Oct 2012, Salvador, Brazil. 7611, pp.253-266, 2012, Lecture Notes in Computer Science. 〈10.1007/978-3-642-33651-5_18〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.sorbonne-universite.fr/hal-00728337
Contributeur : Sébastien Tixeuil <>
Soumis le : mercredi 5 septembre 2012 - 15:50:32
Dernière modification le : jeudi 22 novembre 2018 - 14:40:57
Document(s) archivé(s) le : vendredi 16 décembre 2016 - 11:06:55

Fichiers

papier.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Alexandre Maurer, Sébastien Tixeuil. On Byzantine Broadcast in Loosely Connected Networks. 26th International Symposium on Distributed Computing, DISC 2012, Oct 2012, Salvador, Brazil. 7611, pp.253-266, 2012, Lecture Notes in Computer Science. 〈10.1007/978-3-642-33651-5_18〉. 〈hal-00728337〉

Partager

Métriques

Consultations de la notice

557

Téléchargements de fichiers

430