MAURER Alexandre

PhD student at Sorbonne University
Team : NPA
https://lip6.fr/Alexandre.Maurer

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

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)

Departure date : 12/31/2014

2011-2016 Publications