Self-stabilization

(8th-June-2021)

The idea of self-stabilization in distributed computing was first proposed by Dijkstra in 1974. The concept of self-stabilization is that, regardless of its initial state, the system is guaranteed to converge to a legitimate state in a bounded amount of time by itself without any outside intervention. A non-self-stabilizing system may never reach a legitimate state or it may reach a legitimate state only temporarily. The main complication in designing a self-stabilizing distributed system is that nodes do not have a global memory that they can access instantaneoulsy. Each node must make decisions based on the local knowledge available to it and actions of all nodes must achieve a global objective. The definition of legitimate and illegitimate states depends on the particular application. Generally, all illegitimate states are defined to be those states which are not legitimate states.