Direction de recherche : Sébastien TIXEUIL

Communication fiable dans les réseaux multi-sauts en présence de fautes Byzantines

À mesure que les réseaux s'étendent, ils deviennent de plus en plus susceptibles de défaillir. En effet, leurs nœuds peuvent être sujets à des attaques, pannes, corruptions de mémoire... Afin d'englober tous les types de fautes possibles, nous considérons le modèle le plus général possible : le modèle Byzantin, où les nœuds fautifs ont un comportement arbitraire (et donc, potentiellement malveillant). De telles fautes sont extrêmement dangereuses : un seul nœud Byzantin, s'il n'est pas neutralisé, peut déstabiliser l'intégralité du réseau.

Nous considérons le problème d'échanger fiablement des informations dans un réseau multi-sauts malgré la présence de telles fautes Byzantines. Des solutions existent mais nécessitent un réseau dense, avec un grand nombre de voisins par nœud. Dans cette thèse, nous proposons des solutions pour les réseaux faiblement connectés, tels que la grille, où chaque nœud a au plus 4 voisins.

Dans une première partie, nous acceptons l'idée qu'une minorité de nœuds corrects échouent à communiquer fiablement. En contrepartie, nous proposons des solutions qui tolèrent un grand nombre de fautes Byzantines dans les réseaux faiblement connectés. Dans une seconde partie, nous proposons des algorithmes qui garantissent une communication fiable entre tous les nœuds corrects, pourvu que les nœuds Byzantins soient suffisamment distants. Enfin, nous généralisons des résultats existants à de nouveaux contextes : les réseaux dynamiques, et les réseaux de taille non-bornée.

Soutenance : 20/11/2014

Membres du jury :

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)

Publications 2011-2016

• 2016
  • A. Maurer, S. Tixeuil : “Tolerating Random Byzantine Failures in an Unbounded Network”, Parallel Processing Letters, vol. 26 (1), pp. 1650003, (World Scientific Publishing) (2016)
• 2015
  • A. Maurer, X. Défago, S. Tixeuil : “Communicating Reliably in Multihop Dynamic Networks despite Byzantine Failures”, Proceedings of the International Symposium on Reliable Distributed Systems (SRDS2015), Montreal, Canada, (IEEE Press) (2015)
  • A. Maurer, X. Défago, S. Tixeuil : “Communication fiable dans un réseau dynamique en présence de fautes Byzantines”, ALGOTEL 2015 — 17^es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Beaune, France (2015)
  • A. Maurer, S. Tixeuil : “Containing Byzantine Failures with Control Zones”, IEEE Transactions on Parallel and Distributed Systems, vol. 26 (2), pp. 362-370, (Institute of Electrical and Electronics Engineers) (2015)
• 2014
  • A. Maurer : “Communication fiable dans les réseaux multi-sauts en présence de fautes Byzantines”, soutenance de thèse, soutenance 20/11/2014, direction de recherche Tixeuil, Sébastien (2014)
  • A. Maurer, S. Tixeuil : “Byzantine broadcast with fixed disjoint paths”, Journal of Parallel and Distributed Computing, vol. 74 (11), pp. 3153-3160, (Elsevier) (2014)
  • A. Maurer, S. Tixeuil : “Self-stabilizing Byzantine Broadcast”, Proceedings of the 33^rd IEEE Symposium on Reliable Distributed Systems (SRDS 2014), Nara, Japan, pp. 152-160, (IEEE) (2014)
  • A. Maurer, S. Tixeuil, X. Défago : “Reliable Communication in a Dynamic Network in the Presence of Byzantine Faults”, (2014)
• 2013
  • A. Maurer, S. Tixeuil : “Tolérer les fautes Byzantines dans les graphes planaires”, 15^es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), Pornic, France, pp. 1-4 (2013)
  • A. Maurer, S. Tixeuil : “Dependable Information Broadcast in Sparsely Connected Networks”, International Conference on Latin American Dependable Computing, LADC 2013, Rio de Janeiro, Brazil, pp. 31-39 (2013)
  • A. Maurer, S. Tixeuil : “On Byzantine Broadcast in Planar Graphs”, (2013)
  • A. Maurer, S. Tixeuil : “A Scalable Byzantine Grid”, International Conference on Distributed Computing and Networking, vol. 7730, Lecture Notes in Computer Science, Mumbai, India, pp. 87-101, (Springer) (2013)
• 2012
  • A. Maurer, S. Tixeuil : “On Byzantine Broadcast in Loosely Connected Networks”, 26^th International Symposium on Distributed Computing, DISC 2012, vol. 7611, Lecture Notes in Computer Science, Salvador, Brazil, pp. 253-266 (2012)
  • A. Maurer, S. Tixeuil : “Limiting Byzantine Influence in Multihop Asynchronous Networks”, International Conference on Distributed Computing Systems, Macau, China, pp. 183-192 (2012)
  • A. Maurer, S. Tixeuil : “Confinement de fautes Byzantines dans les réseaux multi-sauts asynchrones”, 14^es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), La Grande Motte, France (2012)
  • A. Maurer, S. Tixeuil : “Parameterizable Byzantine Broadcast in Loosely Connected Networks”, (2012)
• 2011
  • A. Maurer, S. Tixeuil : “Limiting Byzantine Influence in Multihop Asynchronous Networks”, (2011)