Superstabilization


Superstabilization

Superstabilization in computer science is a specialization of the concept of self-stabilization. The difference is that a passage predicate is satisfied while the system undergoes a topological change. Thus, a superstabilizing protocol is said to be "more stable" than a general self-stabilizing protocol that is not superstabilizing. As a result, a better service of the system is provided, given that no severe faults happen. Superstabilization is a popular technique within the scientific community.

Definition

According to [ Shlomi Dolev and Ted Herman. [http://cjtcs.cs.uchicago.edu/articles/1997/4/contents.html Superstabilizing protocols for dynamic distributed systems] . Chicago Journal of Theoretical Computer Science, 4, December 1997. Special Issue on Self-Stabilization] [Self-Stabilization. Shlomi Dolev, MIT Press, 2000.] a protocol P is "superstabilizing" with respect to a class Lambda of topological change events if and only if
# P is self-stabilizing, and
# for every trajectory Phi beginning at a legitimate state and containing a single topology change event of type Lambda, the "passage predicate" holds for every sigma in Phi.

Meaning

Topological changes in self-stabilizing protocols are generally viewed as errors with the consequence, that no guarantees are given until the system has eventually converged into a "correct state". In dynamic distributed systems this assumption is impractical as reconfigurations of the system topology are common and should not disrupt the system in whole. Superstabilizing protocols guarantee that during system reconfiguration (according to reconfiguration events of type Lambda) a passage predicate is satisified that, although weaker than that of a correct system, is sill strong enough to be useful.

Superstabilizing protocols are classified by "stabilization time", "superstabilization time", and "adjustment measure".

References


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Self-stabilization — is a concept of fault tolerance in distributed computing. Distributed computing systems are challenging to debug and analyze. As a result, strong properties (properties that hold under a variety of circumstances) of such systems are especially… …   Wikipedia

  • Structural stability — In mathematics, structural stability is an aspect of stability theory concerning whether a given function is sensitive to a small perturbation. The general idea is that a function or flow is structurally stable if any other function or flow close …   Wikipedia