Tolerating Byzantine failures in sparse networks

Speaker : Alexandre Maurer
Date: 18/09/2013
Time: 2:00 pm - 3:30 pm
Location: LINCS Meeting Room 40


As network grow larger and larger, they become more likely to fail locally. Indeed, the nodes may be subject to attacks, failures, memory corruption… In order to encompass all possible types of failures, we consider the more general model of failure: the Byzantine model, where the failing nodes have an arbitrary malicious behavior. In other words, tolerating Byzantine nodes implies to ensure that there exists no strategy (however unlikely it may be) for the Byzantine nodes to destabilize the network.We thus consider the probleme of reliably broadcasting a message in a multihop network that is subject to Byzantine failures. Solutions exist, but require a highly-connected network. In this talk, we present our recent solutions for Byzantine-resilient broadcast in sparse networks, where each node has a very limited number of neighbors. A typical example is the grid, where each node has at most 4 neighbors. We thus show the tradeo-ff between connectivity and reliability.