Skip to Main content Skip to Navigation
Journal articles

Containing Byzantine Failures with Control Zones

Abstract : 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.
Complete list of metadata
Contributor : Sébastien Tixeuil Connect in order to contact the contributor
Submitted on : Thursday, March 5, 2015 - 11:50:29 AM
Last modification on : Sunday, June 26, 2022 - 9:42:40 AM



Alexandre Maurer, Sébastien Tixeuil. Containing Byzantine Failures with Control Zones. IEEE Transactions on Parallel and Distributed Systems, Institute of Electrical and Electronics Engineers, 2015, 26 (2), pp.362-370. ⟨10.1109/TPDS.2014.2308190⟩. ⟨hal-01123661⟩



Record views