Direction de recherche : Franck PETIT, Lélia BLIN

Optimisation de la Mémoire pour Algorithmes Distribués Auto-Stabilisants

L’auto-stabilisation est un paradigme adapté aux systèmes distribués, particulièrement susceptibles de subir des fautes transitoires. Des erreurs de corruption de mémoire, de messages, la rupture d’un lien de communication peuvent plonger le système dans un état incohérent. Un protocole est auto-stabilisant si, quel que soit l’état initial du système, il garantit un retour à un fonctionnement normal en temps fini.
Plusieurs contraintes s’appliquent aux algorithmes conçus pour les systèmes distribués. L’asynchronie en est un exemple emblématique. Avec le développement de réseaux d’objets connectés, censés être autonomes, il devient également central de concevoir des algorithmes ayant un faible coût en termes de consommation énergétique et peu exigeant en termes de ressources.
Une des manières d’appréhender ces problèmes est de chercher à réduire la taille des messages échangés entre les différents nœuds du réseau. Cette thèse se concentre sur l’optimisation de la mémoire nécessaire à la communication pour les algorithmes distribués auto-stabilisants.
Nous établissons dans cette thèse plusieurs résultats négatifs, démontrant l’impossibilité de résoudre certains problèmes sans une certaine taille minimale pour les messages échangés, en établissant une impossibilité d’utiliser jusqu’au bout l’existence d’identifiants uniques dans le réseau en dessous de cette taille minimale. Ces résultats sont génériques et peuvent s’appliquer à de nombreux problèmes distribués. Dans un second temps, nous proposons des algorithmes particulièrement efficaces en mémoire pour la résolution de deux problèmes fondamentaux des systèmes distribués: la détection de terminaison, et la circulation perpétuelle de jeton.

Publications 2022-2024

• 2024
  • L. Blin, G. Le Bouder, F. Petit : “Optimal Memory Requirement for Self-Stabilizing Token Circulation”, Lecture Notes in Computer Science (LNCS), Springer, Salerno, Italy (2024)
• 2023
  • G. Le Bouder : “Memory-Optimization for Self-Stabilizing Distributed Algorithms”, thèse, soutenance 06/01/2023, direction de recherche Petit, Franck Blin, Lélia (2023)
  • L. Blin, C. Johnen, G. Le Bouder, F. Petit : “Silent Anonymous Snap-Stabilizing Termination Detection”, 2022 41^st International Symposium on Reliable Distributed Systems (SRDS), Vienna, Austria, pp. 156-165, (IEEE), (ISBN: 978-1-6654-9753-4) (2023)
  • L. Blin, L. Feuilloley, G. Le Bouder : “Optimal Space Lower Bound for Deterministic Self-Stabilizing Leader Election Algorithms”, Discrete Mathematics and Theoretical Computer Science, vol. 25 (1), LIPIcs, pp. 5, (DMTCS) (2023)
• 2022
  • L. Blin, L. Feuilloley, G. Le Bouder : “Borne inférieure optimale pour la complexité spatiale des algorithmes déterministes auto-stabilisants d’élection”, AlgoTel 2022 - 24^es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Saint-Rémy-Lès-Chevreuse, France (2022)
  • L. Blin, C. Johnen, G. Le Bouder, F. Petit : “Détection de terminaison silencieuse, anonyme, stabilisante instantanément”, AlgoTel 2022 - 24^es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Saint-Rémy-Lès-Chevreuse, France (2022)