On Byzantine Broadcast in Planar Graphs
This work addresses decentralized communication security in loosely connected networks, but it is incremental as it extends prior results to a broader graph class.
The paper tackles the problem of reliable broadcast in asynchronous networks with Byzantine failures by generalizing a previous result from torus networks to 4-connected planar graphs, showing that broadcast can be guaranteed when the minimal distance between Byzantine nodes exceeds the maximal number of edges per polygon, with time complexity matching simple broadcast and linear memory scaling.
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. Important disclaimer: these results have NOT yet been published in an international conference or journal. This is just a technical report presenting intermediary and incomplete results. A generalized version of these results may be under submission.