Autostabilisation
Un article de Wikipédia, l'encyclopédie libre.
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 canal 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 exemple circulation sans fin d'un jeton sur chaque site), alors l'algorithme retrouvera en temps fini une séquence de configuration 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 exécution correcte légitime.
Le concept d'autostabilisation a été formulé pour la première fois par Dijkstra en 1974.
