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

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

Résumé

We consider the following problem: two nodes want to reliably communicate in a dynamic multihop network where some nodes have been compromised, and may have a totally arbitrary and unpredictable behavior. These nodes are called Byzantine. We consider the two cases where cryptography is available and not available. We prove the necessary and sufficient condition (that is, the weakest possible condition) to ensure reliable communication in this context. Our proof is constructive, as we provide Byzantine-resilient algorithms for reliable communication that are optimal with respect to our impossibility results. In a second part, we investigate the impact of our conditions in three case studies: participants interacting in a conference, robots moving on a grid and agents in the subway. Our simulations indicate a clear benefit of using our algorithms for reliable communication in those contexts.
Fichier principal
Vignette du fichier
paper.pdf (608.98 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-00940569v4⟩
455 Consultations
567 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More