LE BOUDER Gabriel
Supervision : Franck PETIT, Lélia BLIN
Memory-Optimization for Self-Stabilizing Distributed Algorithms
Self-stabilization is a suitable paradigm for distributed systems, particularly prone to transient faults. Errors such as memory or messages corruption, break of a communication link, can put the system in an inconsistent state. A protocol is self-stabilizing if, whatever the initial state of the system, it guarantees that it will return a normal behavior in finite time.
Several constraints concern algorithms designed for distributed systems. Asynchrony is one emblematic example. With the development of networks of connected, autonomous devices, it also becomes crucial to design algorithms with a low energy consumption, and not requiring much in terms of resources.
One way to address these problems is to aim at reducing the size of the messages exchanged between the nodes of the network. This thesis focuses on the memory optimization of the communication for self-stabilizing distributed algorithms.
We establish in this thesis several negative results, which prove the impossibility to solve some problems under a certain limit on the size of the exchanged messages, by showing an impossibility to fully use the presence of unique identifiers in the network below that minimal size. Those results are generic, and may apply to numerous distributed problems. Secondly, we propose particularly efficient algorithms in terms of memory for two fundamental problems in distributed systems: the termination detection, and the token circulation.
Defence : 01/06/2023 - 14h - Campus Pierre et Marie Curie, salle Jacques Pitrat (25-26/105)
Jury members :
Stéphane Devismes, Université de Picardie [Rapporteur]
Christian Scheideler, Université de Padenborn [Rapporteur]
Nicolas Hanusse, LaBRI, CNRS
Alessia Milani, Aix-Marseille Université
Sébastien Tixeuil, Sorbonne Université
Lélia Blin, LIP6, Université d'Évry
Franck Petit, Sorbonne Université
- G. Le Bouder : “Memory-Optimization for Self-Stabilizing Distributed Algorithms”, thesis, defence 01/06/2023, supervision Petit, Franck Blin, Lélia (2023)
- L. Blin, C. Johnen, G. Le Bouder, F. Petit : “Silent Anonymous Snap-Stabilizing Termination Detection”, 2022 41st 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)
- 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 - 24es 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 - 24es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Saint-Rémy-Lès-Chevreuse, France (2022)