Superstabilisering
Superstabilisering är ett koncept för feltolerans i distribuerad datoranvändning . Superstabiliserande distribuerade algoritmer kombinerar funktionerna hos självstabiliserande algoritmer och dynamiska algoritmer . En superstabiliserande algoritm – precis som alla andra självstabiliserande algoritmer – kan startas i ett godtyckligt tillstånd, och den kommer så småningom att konvergera till ett legitimt tillstånd. Dessutom kommer en superstabiliserande algoritm att återhämta sig snabbt från en enda förändring i nätverkstopologin (lägga till eller ta bort en kant eller nod i nätverket).
Vilken självstabiliserande algoritm som helst återhämtar sig från en förändring i nätverkstopologin – systemkonfigurationen efter en topologiändring kan behandlas precis som vilken annan godtycklig startkonfiguration som helst. I en självstabiliserande algoritm kan emellertid konvergensen efter en enda förändring i nätverkstopologin vara lika långsam som konvergensen från ett godtyckligt starttillstånd. I studiet av superstabiliserande algoritmer ägnas särskild uppmärksamhet åt den tid det tar att återhämta sig från en enda förändring i nätverkstopologin.
Definitioner
Stabiliseringstiden för en superstabiliserande algoritm definieras exakt som i fallet med självstabiliserande algoritm: hur lång tid det tar att konvergera till ett legitimt tillstånd från en godtycklig konfiguration . Beroende på beräkningsmodellen mäts tiden t.ex. i synkrona kommunikationsrundor eller i asynkrona cykler.
Superstabiliseringstiden är tiden för att återhämta sig från en enda topologiförändring . Det antas att systemet initialt är i en legitim konfiguration. Då ändras nätverkstopologin; superstabiliseringstiden är den maximala tid det tar för systemet att nå en legitim konfiguration igen. På samma sätt justeringsmåttet det maximala antalet noder som måste ändra sitt tillstånd efter sådana ändringar.
De "nästan legitima konfigurationer" som inträffar efter en topologiändring kan formellt modelleras genom att använda passagepredikat : ett passagepredikat är ett predikat som gäller efter en enda förändring i nätverkstopologin, och även under konvergensen till en legitim konfiguration.
- Dolev, Shlomi ; Herman, Ted (1997), "Superstabiliserande protokoll för dynamiska distribuerade system", Chicago Journal of Theoretical Computer Science, artikel 4.
- Dolev, Shlomi (2000), Self-Stabilization , MIT Press , ISBN 0-262-04178-2 , Avsnitt 7.1.