Français Anglais
Accueil Annuaire Plan du site
Home > Research results > Dissertations & habilitations
Research results
Ph.D de

Group : Parallelism

Efficient Self-stabilization

Starts on 01/09/1995
Advisor : BEAUQUIER, Joffroy

Funding :
Affiliation : Université Paris-Saclay
Laboratory : LRI

Defended on 02/01/2000, committee :
Joffroy Beauquier
Dominique Gouyou-Beauchamps
Christian Lavault
Michel Raynal
Vincent Villain

Research activities :
   - Distributed algorithms
   - Self-stabilisation
   - Randomized algorithms
   - Graph Theory
   - Complexity

Abstract :
When a distributed system is subject to transient failures that arbitrarily modify its state, it is crucial to recover a correct behavior within finite time. Self-stabilization offers such a guarantee, but usually uses large resources. In this thesis, we focus on minimizing these resources when such solutions exist.

We introduced the concept of transient failure detectors, oracles that are called by processors, which notify if transient failures occurred within constant time. Our implementation enables classifying classic problems according to the specific resources dedicated to error detection.
A natural extension was to show that a local property on the local code executed by each processor is sufficient to guarantee self-stabilization of the whole system, whatever the computation assumptions and communication graph may be. Since the original algorithm is not modified, it is overhead-free. Similarly, we developed two synchronizers that enable dynamic tasks to be solved self-stabilizingly, whose memory overhead is constant. Moreover, one of them is snap-stabilizing. Finally, we presented a general technique to systematically reduce the communication
cost, assuming a bounded retransmission delay, and we gave a general framework and tools to design self-stabilizing algorithms in this context.

More information: