Selfstabilisation

Self-stabilisation is a property of distributed systems that describes their ability to automatically recover from any transient fault and return to a legitimate state. A self-stabilising system, when placed in any state, will eventually reach a correct, legitimate state without external intervention. This recovery mechanism is inherent to the system's design.

The concept was introduced by Edsger W. Dijkstra in 1974. In a self-stabilising system, the system's behaviour is defined by a set of rules that are executed by its components. These rules are designed such that regardless of the initial configuration of the system, it will eventually converge to a state where all components are operating correctly and consistently with the system's specification.

Self-stabilising algorithms are often characterised by their ability to handle transient faults, such as temporary network outages, memory corruption, or processor glitches, which can disrupt the normal operation of a distributed system. Once the fault is removed, the system automatically corrects itself. This resilience makes self-stabilisation an important property for building highly reliable and fault-tolerant distributed systems.

Examples of self-stabilising systems include algorithms for mutual exclusion, leader election, and token passing in networks. The key idea is that the system's state transitions are deterministic and are designed to always move the system towards a legitimate configuration. Even if the system enters an illegal state due to a fault, the underlying rules will eventually guide it back to a valid state.