Self-stabilization
From Free net encyclopedia
Self-stabilization is a concept from computer science. The objective of self-stabilization is for a distributed computer system that enters an illegitimate (e.g. erroneous or suboptimal) state recovers back to a legitimate state within a finite time without any external (e.g. human) intervention.
Such a behaviour is very desirable in modern computer and telecommunications network since it would enable them to repair errors and return to normal operations on their own. Computer crashes and network failures could be made fault-tolerance.
The idea of self-stabilization originates from a classic paper by E.W. Dijkstra in 1974 (see reference [1]). Thirty years later, this concept gains importance again since it presents an important foundation for self-managing computer systems and fault-tolerant systems.
An appealing property of self-stabilizing algorithms is that they do not explicitly detect errors to repair them subsequently. Instead, they constantly push the system towards a legitimate state. Since detecting an error is often very difficult and time-consuming, such a behaviour is highly desirable.
The complexity of a self-stabilizing algorithm is measured in (asynchronous) rounds or cycles. A round is a shortest execution trace where each processor executes at least one step. Similarly, a cycle is a shortest execution trace where each processor executes at least one complete iteration of its repeatedly executed list of commands.
Another nice thing with self-stabilizing algorithms is that they can be layered for composition if they do not exhibit any circular dependencies. The stabilization time of the composition is then bounded by the sum of the individual stabilization times of each layer.
Definition
A system is self-stabilizing if
- Starting from any state, it is guaranteed that the system will eventually reach a correct state (convergence).
- Given that the system is in a correct state, it is guaranteed to stay in a correct state, provided that no fault happens (closure).
A system is said to be randomized self-stabilizing if it is self-stabilizing and the expected number of rounds needed to reach a correct state is bounded by some constant <math>k</math> [2].
A self-stabilizing algorithm is silent if it converges to a global state where communication (i.e., the values stored in registers or send via messages) remains constant [4].
Related Work
An extension of the concept of self-stabilization is that of superstabilization [3]. The intent here is to cope with dynamic distributed systems that undergo topological changes. In classical self-stabilization theory arbitrary changes are viewed as errors where no guarantees are given until the system has stabilized again. With superstabilizing systems, there is a passage predicate that is always satisfied, when the system's topology is reconfigured.
References
[2] Self-Stabilization. Shlomi Dolev, MIT Press, 2000.
[3] Shlomi Dolev and Ted Herman. Superstabilizing protocols for dynamic distributed systems. Chicago Journal of Theoretical Computer Science, 4, December 1997. Special Issue on Self-Stabilization.
[4] Shlomi Dolev, Mohamed G. Gouda, and Marco Schneider. Memory requirements for silent stabilization. In PODC '96: Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, pages 27--34, New York, NY, USA, 1996. ACM Press.