Superstabilization

From Wikipedia, the free encyclopedia

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.

[edit] Definition

According to [1][2] a protocol P is superstabilizing with respect to a class Λ of topological change events if and only if

  1. P is self-stabilizing, and
  2. for every trajectory Φ beginning at a legitimate state and containing a single topology change event of type Λ, the passage predicate holds for every \sigma \in \Phi.

[edit] 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 Λ) 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.

[edit] References

  1. ^ 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
  2. ^ Self-Stabilization. Shlomi Dolev, MIT Press, 2000.