Cognitive Networks: Towards Self-Aware Networks

4.7. Self-Stabilization

4.7.1. Concept of Self-Stabilization

A primary characteristic of any distributed system is that the global system behavior is a manifestation of individual component behaviors and their effects on the environment. As expected, in large scale such complex interactions are difficult to abstract and control, and could indeed result in undesirable global system states. When considering a distributed system as a set of states (current configuration and system properties) and the transitions among states (system behaviors), then the property of stabilization categorizes the set of states as legitimate or illegitimate states. A legitimate state is one where the configuration of the system is consistent and its functions desirable.

The concept of self-stabilization was first introduced in 1973 by Dijkstra ^[]. He describes a self-stabilizing system as a distributed system where individual component behaviors are determined by a subset of global system state that is known to the component and the global system must exhibit the property of 'regardless of its initial state, it is guaranteed to arrive at a legitimate state in a finite number of steps'. Two key properties are: (1) the system could initiate in any state and (2) the system can always recover from transient faults. When discussing self-stabilization, the concept of closure and convergence ^[] are often mentioned. The closure property states that if the system is stable, after a number of executions it will ...