Superstabilisierung

Superstabilisierung ist eine Art von Fehlertoleranz in verteilten Systemen. Superstabilisierende Algorithmen kombinieren die Eigenschaften von selbst-stabilisierenden Algorithmen und dynamischen Algorithmen. Ein superstabilisierender Algorithmus kann in einem beliebigen Zustand gestartet werden und konvergiert letztendlich zu einem legitimen Zustand. Zusätzlich stellt ein superstabilisierender Algorithmus sehr schnell wieder einen legitimen Zustand her, nachdem er einen solchen aufgrund einer einfachen Änderung verlassen hat (durch Hinzufügen oder Entfernen einer Kante oder eines Knotens in der Netzwerktopologie).

Ein selbst-stabilisierender Algorithmus leitet eine Wiederherstellung nach einer Änderung der Netzwerktopologie ein. Die neue Systemkonfiguration kann wie eine Startkonfiguration behandelt werden. Bei einem lediglich selbst-stabilisierendem Algorithmus ist die Konvergenz nach einer einfachen Änderung im Allgemeinen jedoch so langsam wie die Konvergenz von einer beliebigen Startkonfiguration. Beim Studieren superstabilisierender Algorithmen wird hingegen besonderes Augenmerk auf die erforderliche Zeit zur Wiederherstellung eines legitimen Zustands nach einer solchen einfachen Änderung in der Netzwerktopologie gelegt.

Definitionen

Die Stabilisierungszeit eines superstabilisierenden Algorithmus ist wie bei einem selbst-stabilisierenden Algorithmus definiert als die maximale Zeit von einer beliebigen Startkonfiguration bis zum Erreichen eines legitimen Zustands. Abhängig vom Berechnungsmodell wird diese Zeit in synchronen Kommunikationsrunden oder asynchronen Zyklen gemessen.

Die Superstabilisierungszeit ist die maximale Zeit zum Erreichen eines (evtl. anderen) legitimen Zustands nach einer einfachen Änderung der Netzwerktopologie, vorausgesetzt das System befand sich zuvor bereits in einem legitimen Zustand. Das Anpassungsmaß (engl. adjustment measure) ist die maximale Anzahl der Knoten, deren Zustand dafür geändert werden muss.

Literatur

• Shlomi Dolev: Self-Stabilization. MIT Press, 2000, ISBN 0-262-04178-2, Abschnitt 7.1.