A Scalable Byzantine Grid

Abstract : Modern networks assemble an ever growing number of nodes. However, it remains difficult to increase the number of channels per node, thus the maximal degree of the network may be bounded. This is typically the case in grid topology networks, where each node has at most four neighbors. In this paper, we address the following issue: if each node is likely to fail in an unpredictable manner, how can we preserve some global reliability guarantees when the number of nodes keeps increasing unboundedly ? To be more specific, we consider the problem or reliably broadcasting information on an asynchronous grid in the presence of Byzantine failures -- that is, some nodes may have an arbitrary and potentially malicious behavior. Our requirement is that a constant fraction of correct nodes remain able to achieve reliable communication. Existing solutions can only tolerate a fixed number of Byzantine failures if they adopt a worst-case placement scheme. Besides, if we assume a constant Byzantine ratio (each node has the same probability to be Byzantine), the probability to have a fatal placement approaches 1 when the number of nodes increases, and reliability guarantees collapse. In this paper, we propose the first broadcast protocol that overcomes these difficulties. First, the number of Byzantine failures that can be tolerated (if they adopt the worst-case placement) now increases with the number of nodes. Second, we are able to tolerate a constant Byzantine ratio, however large the grid may be. In other words, the grid becomes scalable. This result has important security applications in ultra-large networks, where each node has a given probability to misbehave.
Type de document :
Communication dans un congrès
International Conference on Distributed Computing and Networking, Jan 2013, Mumbai, India. Springer, 7730, pp.87-101, 2013, Lecture Notes in Computer Science. 〈10.1007/978-3-642-35668-1_7〉
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-00742655
Contributeur : Sébastien Tixeuil <>
Soumis le : mardi 16 octobre 2012 - 17:48:34
Dernière modification le : jeudi 22 novembre 2018 - 14:11:16
Document(s) archivé(s) le : samedi 17 décembre 2016 - 02:18:15

Fichiers

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

Identifiants

Collections

Citation

Alexandre Maurer, Sébastien Tixeuil. A Scalable Byzantine Grid. International Conference on Distributed Computing and Networking, Jan 2013, Mumbai, India. Springer, 7730, pp.87-101, 2013, Lecture Notes in Computer Science. 〈10.1007/978-3-642-35668-1_7〉. 〈hal-00742655〉

Partager

Métriques

Consultations de la notice

517

Téléchargements de fichiers

331