Description
Date depot: 12 avril 2023
Titre: Computation of Lower Bounds and construction of optimal memory algorithm in Self-Stabilization
Directrice de thèse:
Lélia BLIN (IRIF)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Systèmes et réseaux
Resumé: Self-stabilization is a paradigm suited to asynchronous distributed systems prone to transient failures. The occurrence of such a failure (e.g., memory corruption) may move the system to an arbitrary configuration, and an algorithm is self-stabilizing if it guarantees that whenever the system is in a configuration that is illegal with respect to some given boolean predicate Π, the system returns to a legal configuration in finite time (and remains in legal configuration as long as no other failures occur). Introduced in 1974 by Edsger Dijkstra, self-stabilization was promoted by Leslie Lamport (Turing Award winner in 2014) in the 1980s, with the latter considering his promotion of Dijkstra's ideas as 'one of my greatest contributions to computer science'.
The question addressed in this these is: under which circumstances is it possible to reach a space complexity as low as the size of the labels? And if not, what is the smallest space complexity that can be achieved? More specifically, we will focus on various problems such as:
What is the minimum memory required to encode pointers to neighbors in order to encode spanning trees (BFS, DFS)?
What are the minimum bounds for different problems such as tree construction or cluster construction?
We will approach these problems with different metrics such as the number of nodes, the degree of the graph, and the diameter of the graph.