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 may exhibit unpredictable malicious behavior. We focus on completely decentralized solutions. Few Byzantine-robust algorithms exist for loosely connected networks. A recent solution guarantees reliable broadcast on a torus when D > 4, D being the minimal distance between two Byzantine nodes. In this paper, we generalize this result to 4-connected planar graphs. We show that reliable broadcast can be guaranteed when D > Z, Z being the maximal number of edges per polygon. We also show that this bound on D is a lower bound for this class of graphs. Our solution has the same time complexity as a simple broadcast. This is also the first solution where the memory required increases linearly (instead of exponentially) with the size of transmitted information.
Fichier principal
Vignette du fichier
bare_conf.pdf (261.62 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-00773343v3⟩
505 View
407 Download



Gmail Facebook X LinkedIn More