Skip to Main content Skip to Navigation

On Byzantine Broadcast in Planar Graphs

Abstract : 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).
Complete list of metadatas
Contributor : Alexandre Maurer <>
Submitted on : Sunday, January 13, 2013 - 11:35:39 AM
Last modification on : Friday, January 8, 2021 - 5:38:04 PM
Long-term archiving on: : Saturday, April 1, 2017 - 4:17:24 AM


Files produced by the author(s)


  • HAL Id : hal-00773343, version 1
  • ARXIV : 1301.2875


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



Record views


Files downloads