JEANNEAU Denis

Docteur
Équipe : DELYS
Date de départ : 25/12/2018
https://lip6.fr/Denis.Jeanneau

Direction de recherche : Pierre SENS

Co-encadrement : ARANTES Luciana

Détecteurs de fautes pour les systèmes distribués dynamiques

Dans le problème du consensus, tous les processus corrects du système doivent se mettre d'accord sur une unique valeur. Le problème du k-accord est une généralisation du consensus dans laquelle les processus peuvent se mettre d'accord sur au plus k valeurs. Le problème de l'exclusion mutuelle nécessite de permettre aux processus l'accès à une section critique, tout en garantissant qu'au plus un processus peut se trouver en section critique à tout moment. Ces problèmes fondamentaux de l'algorithmique distribuée ont été largement étudiés, mais la plupart des solutions existantes s'appuient sur l'hypothèse implicite que le système n'est pas dynamique.
Traditionellement, l'algorithmique distribuée consiste à étudier des systèmes distribués dans lesquels la liste des participants est statique et le graphe de communication est connecté, voire complet. Mais afin de modéliser les réseaux modernes, tels que les réseaux pair-à-pair ou sans fil, il est nécessaire de considérer une nouvelle sorte de systèmes distribués. Les systèmes dynamiques sont des systèmes distribués dans lesquels (1) les processus peuvent rejoindre ou quitter le système en cours d'exécution, et (2) le graphe de communication évolue au fil du temps.
L'abstraction des détecteurs de fautes a été introduite afin de contourner l'impossibilité de résoudre le consensus dans les systèmes asynchrones sujets aux pannes franches. Un détecteur de fautes est un oracle local fournissant aux processus des informations non fiables sur les pannes de processus. Mais un détecteur de fautes qui est suffisant pour résoudre un problème donné dans un système statique n'est pas nécessairement suffisant pour résoudre le même problème dans un système dynamique. De plus, certains détecteurs de fautes ne peuvent pas être implémentés dans un système dynamique. Par conséquent, il est nécessaire de redéfinir les détecteurs de fautes existants et de concevoir de nouveaux algorithmes.
Dans cette thèse, nous fournissons une nouvelle définition d'un détecteur de fautes pour le k-accord, et nous prouvons qu'il est suffisant pour résoudre le k-accord dans un système dynamique. Nous définissons également un modèle de système dynamique, ainsi qu'un algorithme capable d'implémenter ce nouveau détecteur de fautes dans notre modèle.
De plus, nous adaptons un détecteur existant pour l'exclusion mutuelle et nous prouvons que même dans les systèmes dynamiques, il s'agit toujours du détecteur de fautes le plus faible pour résoudre l'exclusion mutuelle. Cela signifie que ce détecteur est plus faible que tous les autres détecteurs capables de résoudre l'exclusion mutuelle.

Soutenance : 07/12/2018

Membres du jury :

Carole Delporte, Professeur à l'Université Paris Diderot [Rapporteur]
Roy Friedman, Professeur au Technion, Israel Institute of Technology [Rapporteur]
Arnaud Casteigts, MdC HDR à l'Université de Bordeaux
Sébastien Tixeuil, Professeur à Sorbonne Université
Luciana Arantes, MdC à Sorbonne Université
Pierre Sens, Professeur à Sorbonne Université

Date de départ : 25/12/2018

Publications 2015-2019

Mentions légales
Carte du site