Séminaire REGAL


Présentation des travaux d'Olivier Pérès

Friday, October 30, 2009
Speaker(s) : Olivier Pérès - Post-doctorant Lip6

1. Safer than Safe: On the Initial State of Self-Stabilizing Systems.   Sylvie Delaët, Shlomi Dolev, and Olivier Pérès.   Accepted as a Brief Announcement in SSS, accepted in OPODIS.   Self-stabilizing systems can be started in any arbitrary state and converge to exhibit the desired behavior. However, self-stabilizing systems can be started in predefined initial states, in the same way as non-stabilizing systems. In this case, a self-stabilizing system can mask faults just like any other distributed system. Moreover, whenever faults overwhelm the systems beyond their capabilities to mask faults, the stabilizing system recovers to exhibit eventual safety and liveness, while the behavior of non-stabilizing systems is undefined and may well remain totally and permanently undesired. We demonstrate the importance of defining the initial state of a self-stabilizing system in a specific case of distributed reset over a system composed of several layers of self-stabilizing algorithms. A self-stabilizing stabilization detector ensures that, at first, only the very first layer(s) takes action, and that then higher levels are activated, ensuring smooth restarts, while preserving the stabilization property. The safety of initialized self-stabilizing systems, combined with their better ability to regain safety and liveness following severe conditions, is then demonstrated over the classical fault masking modular redundancy architecture.
2. How to Overcome the Limits of Bounds   Accepted as a Brief Announcement in SSS.   A distributed system consists of processes linked to one another by communication channels. A classical problem is how to model these channels realistically so that it is possible to write correct algorithms. Many algorithms are written under the assumption that the channels deliver the messages in the order in which they were sent, and an unknown arbitrary bound is assumed on the capacity of each channel. This stems from the obervation of a hardware communication link, but raises the need for the algorithms using the channels to cope with these bounds. This article presents a new solution, called IO-fairness, that results in more natural executions and removes the need for artificial workarounds. IO-fairness can be used on individual algorithms and, also importantly, is useful to execute global algorithms made of several composed subalgorithms.

Lamia.Benmouffok (at) nulllip6.fr