Reliable Communication in a Dynamic Network in the Presence of Byzantine Faults - Sorbonne Université
Rapport (Rapport De Recherche) Année : 2014

Reliable Communication in a Dynamic Network in the Presence of Byzantine Faults

Résumé

We consider the problem of transmitting information reliably from a source node to a sink node in a dynamic multihop network, in spite of the presence of Byzantine nodes. Byzantine nodes behave arbitrarily, and can tamper with messages or forward spurious ones. Previous work has shown that, in static multihop networks, reliable communication is possible in the presence of k Byzantine faults if and only if there are 2k+1 node-disjoint paths from the source to the sink. However, this result relies on Menger's theorem (that establishes equivalence between node cut and connectivity), which only holds in static networks. In this paper, we prove a necessary and sufficient condition for reliable communication in dynamic networks, where the topology can vary over time and nodes can be subject to arbitrary Byzantine failures. The positive side of the condition is constructive, as we provide a Byzantine tolerant protocol for multihop communication in dynamic networks. Then, we assess the significance of this condition for several case studies (synthetic movements on agents, actual movements of participants interacting in a conference, movements based on the schedule of the Paris subway) and demonstrate the benefits of our protocol in various contexts.
Fichier principal
Vignette du fichier
bare_conf-copy.pdf (432.05 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00940569 , version 1 (01-02-2014)
hal-00940569 , version 2 (11-02-2014)
hal-00940569 , version 3 (27-05-2014)
hal-00940569 , version 4 (16-02-2015)

Identifiants

Citer

Alexandre Maurer, Sébastien Tixeuil, Xavier Défago. Reliable Communication in a Dynamic Network in the Presence of Byzantine Faults. [Research Report] _. 2014. ⟨hal-00940569v3⟩
543 Consultations
597 Téléchargements

Altmetric

Partager

More