MAURER Alexandre

PhD graduated
Team : NPA
Departure date : 12/31/2014

Supervision : SĂ©bastien TIXEUIL

Reliable communication despite Byzantine failures in sparse networks

As modern networks grow larger and larger, they become more likely to fail. Indeed, their nodes can be subject to attacks, failures, memory corruptions... In order to encompass all possible types of failures, we consider the most general model of failure: the Byzantine model, where the failing nodes have an arbitrary (and thus, potentially malicious) behavior. Such failures are extremely dangerous, as one single Byzantine node, if not neutralized, can potentially lie to the entire network.
We consider the problem of reliably exchanging information in a multihop network despite such Byzantine failures. Solutions exist but require a dense network, where each node has a large number of neighbors. In this thesis, we propose solutions for sparse networks, such as the grid, where each node has at most 4 neighbors.
In a first part, we accept that some correct nodes fail to communicate reliably. In exchange, we propose quantitative solutions that tolerate a large number of Byzantine failures, and significantly outperform previous solutions in sparse networks. In a second part, we propose algorithms that ensure reliable communication between all correct nodes, provided that the Byzantine nodes are sufficiently distant from each other. At last, we generalize existing results to new contexts: dynamic networks, and networks with an unbounded diameter.

Defence : 11/20/2014 - 14h - Site Jussieu 25-26/105

Jury members :

Michel Raynal, (IRISA Rennes) [Rapporteur]
Nicola Santoro, (Carleton University, Canada) [Rapporteur]
Antonio Fernandez Anta, (IMDEA Networks, Espagne)
Rachid Guerraoui, (EPFL, Suisse)
Pierre Sens, (LIP6)
Sébastien Tixeuil, (LIP6)

2011-2016 Publications