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 totally decentralized solutions. Very few Byzantine-robust algorithms exist for loosely connected networks. A recent algorithm 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 is guaranteed when D > Z, Z being the maximal number of edges per polygon. We also show that this bound on D cannot be improved 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 with the size of informations, and not exponentially.
Complete list of metadatas
Contributor : Alexandre Maurer <>
Submitted on : Tuesday, January 22, 2013 - 1:58:01 AM
Last modification on : Friday, January 8, 2021 - 5:38:04 PM
Long-term archiving on: : Saturday, April 1, 2017 - 8:07:41 AM


Files produced by the author(s)


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


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



Record views


Files downloads