SELF-STABILIZATION

In 1973 Dijkstra introduced to computer science the notion of self-sta bilization in the context of distributed systems. He defined a system as self-stabilizing when ''regardless of its initial state, it is guar anteed to arrive at a Iegitimate state in a finite number of steps.'' A system which is not self-stabilizing may stay in an illegitimate sta te forever. Dijkstra's notion of self-stabilization, which originally had a very narrow scope of application, is proving to encompass a form al and unified approach to fault tolerance under a model of transient failures for distributed systems. In this paper we define self-stabili zation, examine its significance in the context of fault tolerance, de fine the important research themes that have arisen from it, and discu ss the relevant results. In addition to the issues arising from Dijkst ra's original presentation as well as several related issues, we discu ss methodologies for designing self-stabilizing systems, the role of c ompilers with respect to self-stabilization, and some of the factors t hat prevent self-stabilization.