Byzantine broadcast with fixed disjoint paths

• We consider the problem of reliably communicating despite Byzantine failures.
• We propose an algorithm designed for sparse networks.
• We give a methodology to determine if two nodes communicate reliably.
• With simulations, we show that our algorithm outperforms previous solutions.

We consider the problem of reliably broadcasting a message in a multihop network. We assume that some nodes may be Byzantine, and behave arbitrarily. We focus on cryptography-free solutions.We propose a protocol for sparse networks (such as grids or tori) where the nodes are not aware of their position. Our protocol uses a fixed number of disjoint paths to accept and forward the message to be broadcast. It can be tuned to significantly improve the number of Byzantine nodes tolerated. We present both theoretical analysis and experimental evaluation.