| 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.
|