CTL
12 December 2013 - 13h30
Self-Stabilizing Algorithms for Constructing Distributed Spanning Structures (Phd Defense)
by Yvan Rivierre from VERIMAG
Abstract: This thesis deals with the self-stabilizing construction of spanning structures over a distributed system. Self-stabilization is a paradigm for fault-tolerance in distributed algorithms. It guarantees that the system eventually satisfies its specification after transient faults hit the system.
Our model of distributed system assumes locally shared memories for communicating, unique identifiers for symmetry-breaking, and distributed daemon for execution scheduling, that is, the weakest proper daemon. More generally, we aim for the weakest possible assumptions, such as arbitrary topologies, in order to propose the most versatile constructions of distributed spanning structures.
We present four original self-stabilizing algorithms achieving k-clustering, (f,g)-alliance construction, and ranking. For every of these problems, we prove the correctness of our solutions. Moreover, we analyze their time and space complexity using formal proofs and simulations. Finally, for the (f,g)-alliance problem, we consider the notion of safe convergence in addition to self-stabilization. It enforces the system to first quickly satisfy a specification that guarantees a minimum of conditions, and then to converge to a more stringent specification.
Jury :
- Franck Petit (Pr à l'UPMC), rapporteur
- Ajoy K. Datta (Pr à l'UNLV), rapporteur
- Alain Cournier (Pr à l'UPJV), examinateur
- Fabien Mathieu (HDR, Alcatel-Lucent Bell Labs France), examinateur
- Florence Maraninchi (Pr à Grenoble-INP), directrice
- Fabienne Carrier (Mcf à l'UJF), co-encadrante
- Stéphane Devismes (Mcf à l'UJF), co-encadrant
