selfstabilising

Self-stabilising refers to a property of a system, often a distributed system, where it can automatically recover from erroneous states and return to a correct, stable state without external intervention. This recovery mechanism is inherent to the system's design. When a system encounters an error, such as a faulty process or message corruption, it enters a transient, incorrect state. A self-stabilising system is guaranteed to eventually reach a well-defined legitimate state, regardless of the initial configuration or the transient errors encountered.

The concept was first introduced by Edsger W. Dijkstra in 1974. The key idea is that the system's processes repeatedly execute rules or operations that, over time, tend to correct any deviations from the legitimate states. The system is said to stabilise if, starting from any possible state, it eventually reaches a legitimate state and remains in one thereafter. Self-stabilisation is a powerful fault-tolerance mechanism, as it does not require knowledge of the specific errors that occurred. The system simply continues to operate according to its rules, and in doing so, it naturally corrects itself. Applications of self-stabilising systems include distributed algorithms for leader election, mutual exclusion, and network routing, where resilience to failures is crucial.