Superstabilization is a concept of

fault-tolerance Fault tolerance is the property that enables a system to continue operating properly in the event of the failure of one or more faults within some of its components. If its operating quality decreases at all, the decrease is proportional to the ...

distributed computing A distributed system is a system whose components are located on different networked computers, which communicate and coordinate their actions by passing messages to one another from any system. Distributed computing is a field of computer sci ...

. Superstabilizing

distributed algorithm A distributed algorithm is an algorithm designed to run on computer hardware constructed from interconnected processors. Distributed algorithms are used in different application areas of distributed computing, such as telecommunications, scientific ...

s combine the features of

self-stabilizing algorithm Self-stabilization is a concept of fault-tolerance in distributed systems. Given any initial state, a self-stabilizing distributed system will end up in a correct state in a finite number of execution steps. At first glance, the guarantee of sel ...

s 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

*, article 4. *{{Citation , last=Dolev , first=Shlomi , authorlink=Shlomi Dolev , title=Self-Stabilization , publisher=

MIT Press The MIT Press is a university press affiliated with the Massachusetts Institute of Technology (MIT) in Cambridge, Massachusetts (United States). It was established in 1962. History The MIT Press traces its origins back to 1926 when MIT publish ...

, year=2000 , isbn=0-262-04178-2 , Section 7.1. Distributed computing problems Fault-tolerant computer systems