  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.
