Autostabilisation
L'autostabilisation est la propriété d'un algorithme réparti capable de retrouver seul un fonctionnement correct après apparition d'une panne transitoire.
Une panne transitoire affecte toute donnée volatile, qu'elle soit en cours d'acheminement (message) ou dans une mémoire. Les mémoires non volatiles (ROM) ne sont pas altérées par les pannes transitoires. De même, sur chaque site, le code des algorithmes est supposé ne pas être modifié par les pannes transitoires. Cela correspond par exemple aux algorithmes câblés, ou bien aux algorithmes régulièrement restaurés depuis un support non volatile. Lorsqu'une telle panne affecte le système, celui-ci peut atteindre un état quelconque.
Si la spécification de l'algorithme réparti concerne un état particulier (par ex. une distance doit être calculée), alors l'algorithme retrouvera une configuration légitime en temps fini après que la panne transitoire a cessé. Pour ce type d'algorithme, la spécification porte sur les configurations du système, c'est-à-dire sur l'état de chaque site et de chaque cannal de communication. L'algorithme autostabilisant retrouve en temps fini une configuration légitime, c'est-à-dire une configuration dans laquelle l'état voulu est réalisé (eg. la distance est calculée et est correcte).
Si la spécification de l'algorithme réparti concerne un comportement particulier (par ex. circulation sans fin d'un jeton sur chaque site), alors l'algorithme retrouvera en temps fini une séquence de configurations dans laquelle le comportement est réalisé (eg. le jeton visite effectivement chaque site). Pour ce type d'algorithme, la spécification porte sur les exécutions (enchaînement de configurations). L'algorithme autostabilisant converge en temps fini vers une execution correcte légitime.
Le concept d'autostabilisation a été formulé pour la première fois par Dijkstra en 1974.
| Image manquante Symbole-ordinateur.png | Portail Informatique - Accédez d'un seul coup d’œil à toute la série des articles de Wikipédia concernant l'informatique. |