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.

Publications 2015-2019

• 2019
  • E. Mauffret, É. Jeanneau, L. Arantes, P. Sens : “The Weakest Failure Detector to Solve the Mutual Exclusion Problem in an Unknown Dynamic Environment”, 20^th International Conference on Distributed Computing and Networking (ICDCN 2019), Bangalore, India (2019)
• 2018
  • D. Jeanneau : “Détecteurs de fautes pour les systèmes distribués dynamiques”, soutenance de thèse, soutenance 07/12/2018, direction de recherche Sens, Pierre, co-encadrement : Arantes, Luciana (2018)
  • E. Mauffret, É. Jeanneau, L. Arantes, P. Sens : “The Weakest Failure Detector to Solve the Mutual Exclusion Problem in an Unknown Dynamic Environment”, (2018)
• 2017
  • É. Jeanneau, Th. Rieutord, L. Arantes, P. Sens : “Détecteur de fautes pour le k-accord dans les systèmes inconnus et dynamiques”, ALGOTEL 2017 - 19^es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Quiberon, France (2017)
• 2016
  • É. Jeanneau, L. Rodrigues, E. Duarte Júnior, L. Arantes : “An Autonomic Hierarchical Reliable Broadcast Protocol for Asynchronous Distributed Systems with Failure Detector”, Latin-American Symposium on Dependable Computing (LADC), Cali, Colombia (2016)
  • É. Jeanneau, Th. Rieutord, L. Arantes, P. Sens : “Solving k-Set Agreement Using Failure Detectors in Unknown Dynamic Networks”, IEEE Transactions on Parallel and Distributed Systems, (Institute of Electrical and Electronics Engineers) (2016)
• 2015
  • É. Jeanneau, Th. Rieutord, L. Arantes, P. Sens : “A Failure Detector for k-Set Agreement in Dynamic Systems”, NCA 2015 - 14^th IEEE International Symposium on Network Computing and Applications, Cambridge, United States, pp. 176-183, (IEEE) (2015)
  • É. Jeanneau, Th. Rieutord, L. Arantes, P. Sens : “A Failure Detector for k-Set Agreement in Asynchronous Dynamic Systems”, (2015)