Containing Byzantine Failures with Control Zones - Sorbonne Université
Journal Articles IEEE Transactions on Parallel and Distributed Systems Year : 2015

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.
No file

Dates and versions

hal-01123661 , version 1 (05-03-2015)

Identifiers

Cite

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

Altmetric

Share

More