Evènement pour le groupe Algorithmique Distribuée


Date 2006-03-13  14:00-15:00
Titre"Observer la stabilisation" 
RésuméLes systèmes auto-stabilisants sont des systèmes répartis naturellement tolérants aux défaillances. Un système auto-stabilisant est un système qui, quelque soit son initialisation et donc après une défaillance, finit par se comporter correctement. Un inconvénient souvent cité de l'auto-stabilisation est que la stabilisation ne peut être détectée par le protocole lui-même. En effet, si la détection se fait par un prédicat sur un ensemble de variables, la corruption de ces variables peut donner une fausse indication. Par contre, rien n'empêche un observateur extérieur de procéder à cette détection. Dans un article de PODC 98, Lin et Simon proposent un observateur réparti et montrent à l'aide d'exemples que la détection peut être plus courte que la stabilisation. L'observateur réparti utilise, en chaque site, une mémoire supposée incorruptible. Cette hypothèse, si elle est valide pour des réseaux locaux de petite taille, ne passe absolument pas à l'échelle. Nous proposons un nouveau modèle, fondé sur des observateurs locaux, utilisant beaucoup moins de ressources. En particulier, un tel observateur est placé sur un seul site du système et permet de conclure, sous certaines conditions, à la stabilisation. Dans ce modèle, nous prouvons qu'il est possible de construire un observateur déterministe pour n'importe quelle tâche spécifiée sous un démon synchrone et pour une topologie distinguée, dès lors que cette tâche admet une solution auto-stabilisante. Nous introduisons également la notion d'observateur probabiliste et nous prouvons que de tels observateurs permettent d'observer une plus grande classe de systèmes auto-stabilisants que les observateurs déterministes.  
LieuSalle 076 
OrateurLaurence Pilard 
Emailpilard@lri.fr 
UrlLRI 



Aucun document lié à cet événement.

Retour
Retour à l'index