On Byzantine Broadcast in Planar Graphs - Sorbonne Université
Rapport Année : 2013

On Byzantine Broadcast in Planar Graphs

Résumé

We consider the problem of reliably broadcasting information in a multihop asynchronous network in the presence of Byzantine failures: some nodes have an unpredictable malicious behavior. We focus on non-crytographic solutions. Very few Byzantine-robust algorithms exist for loosely connected networks. A recent algorithm guarantees reliable broadcast on a lattice when D > 4, D being the minimal distance between two Byzantine nodes. In this paper, we generalize this result to planar graphs where edges delimit convex polygons. We show that reliable broadcast is guaranteed when D > Z, Z being the maximal number of edges per polygon. We also show that no algorithm can improve this bound. In a second part, we assume that the delay between two activations of a correct process has an upper and lower bound. We show that the good information is delivered within a linear time. We also show that reliable broadcast is still guaranteed with a finite memory (exhaustion safety).
Fichier principal
Vignette du fichier
bb_planar.pdf (246.86 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00773343 , version 1 (13-01-2013)
hal-00773343 , version 2 (22-01-2013)
hal-00773343 , version 3 (09-02-2013)
hal-00773343 , version 4 (07-12-2013)

Identifiants

Citer

Alexandre Maurer, Sébastien Tixeuil. On Byzantine Broadcast in Planar Graphs. 2013. ⟨hal-00773343v1⟩
560 Consultations
421 Téléchargements

Altmetric

Partager

More