Super stabilization

Super stabilization is a type of fault tolerance in distributed systems . Super stabilizing algorithms combine the properties of self-stabilizing algorithms and dynamic algorithms. A super stabilizing algorithm can be started in any state and will ultimately converge to a legitimate state. In addition, a super-stabilizing algorithm restores a legitimate state very quickly after leaving it due to a simple change (by adding or removing an edge or a node in the network topology ).

A self-stabilizing algorithm initiates a recovery after a change in the network topology. The new system configuration can be treated like a startup configuration. With an algorithm that is merely self-stabilizing, however, convergence after a simple change is generally as slow as convergence from any starting configuration. On the other hand, when studying super stabilizing algorithms, particular attention is paid to the time required to restore a legitimate state after such a simple change in the network topology.

Definitions

The stabilization time of a super stabilizing algorithm is as defined in a self-stabilizing algorithm as the maximum time from an arbitrary initial configuration until a legitimate state. Depending on the calculation model, this time is measured in synchronous communication rounds or asynchronous cycles.

The super stabilization time is the maximum time to reach a (possibly different) legitimate state after a simple change in the network topology, provided the system was already in a legitimate state. The degree of fitness (engl. Adjustment measure ) is the maximum number of nodes whose state to be changed for need.

literature

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