On Byzantine Broadcast in Planar Graphs - Sorbonne Université Access content directly
Reports Year : 2013

On Byzantine Broadcast in Planar Graphs


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
Origin : Files produced by the author(s)

Dates and 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)



Alexandre Maurer, Sébastien Tixeuil. On Byzantine Broadcast in Planar Graphs. 2013. ⟨hal-00773343v1⟩
505 View
407 Download



Gmail Facebook X LinkedIn More