Containing Byzantine Failures with Control Zones

We consider the problem of reliably broadcasting messages in a network where some nodes are likely to fail. We consider the most general failure model: the Byzantine model, where the failing nodes have an arbitrary behavior, and may actively try to destabilize the network. We focus on totally decentralized solutions. Most existing solutions require high network connectivity, and are not adapted to sparsely connected networks. A typical example is the grid, where each node has at most four neighbors. In this paper, we propose a new broadcast protocol adapted to such networks. This protocol is based on interconnected subsets called control zones, that filter the diffusion of false messages. We give a methodology to determine a set of nodes that always communicate reliably, depending on the placement of Byzantine nodes. We then use this methodology to perform an experimental evaluation on square and hexagonal grids, in the presence of randomly distributed Byzantine failures. We show that our protocol significantly improves the communication probability, compared to existing solutions.