Superstabilization

Superstabilization is a concept of fault-tolerance in distributed computing. Superstabilizing distributed algorithms combine the features of self-stabilizing algorithms and dynamic algorithms. A superstabilizing algorithm – just like any other self-stabilizing algorithm – can be started in an arbitrary state, and it will eventually converge to a legitimate state. Additionally, a superstabilizing algorithm will recover rapidly from a single change in the network topology (adding or removing one edge or node in the network).

Any self-stabilizing algorithm recovers from a change in the network topology – the system configuration after a topology change can be treated just like any other arbitrary starting configuration. However, in a self-stabilizing algorithm, the convergence after a single change in the network topology may be as slow as the convergence from an arbitrary starting state. In the study of superstabilizing algorithms, special attention is paid to the time it takes to recover from a single change in the network topology.

Definitions

The stabilization time of a superstabilizing algorithm is defined exactly as in the case of self-stabilizing algorithm: how long it takes to converge to a legitimate state from an arbitrary configuration. Depending on the computational model, time is measured, e.g., in synchronous communication rounds or in asynchronous cycles.

The superstabilization time is the time to recover from a single topology change. It is assumed that the system is initially in a legitimate configuration. Then the network topology is changed; the superstabilization time is the maximum time it takes for the system to reach a legitimate configuration again. Similarly, the adjustment measure is the maximum number of nodes that have to change their state after such changes.

The “almost-legitimate configurations” which occur after one topology change can be formally modelled by using passage predicates: a passage predicate is a predicate that holds after a single change in the network topology, and also during the convergence to a legitimate configuration.

References

Dolev, Shlomi; Herman, Ted (1997), "Superstabilizing protocols for dynamic distributed systems", Chicago Journal of Theoretical Computer Science, 3: 1–40, doi:10.4086/cjtcs.1997.004, article 4.
Dolev, Shlomi (2000), Self-Stabilization, MIT Press, ISBN 0-262-04178-2, Section 7.1.