On the costs of self-stabilization (Q1098276)

The Dijkstra recovery algorithms for a distributed ring of loosely coupled processors that have entered an illegal state are based on message exchanges that implement the property of self-stabilization. One of these is the k-state algorithm, which depends on one of the processors, called bottom, to be distinct in its behaviour from the others. The processors change their labelling such that regardless of the initial state (labellings) of the processors, they are guaranteed to arrive at a legitimate state. In each round, a central demon chooses a processor which may initiate a message exchange, depending on its labelling relationship to its neighbour. This paper addresses the analysis of the k-state algorithm with respect to the expected number of message passes and the expected number of rounds, given that some rounds will not cause messages to be exchanged. The analysis uses a sub-problem within the k-state algorithm, that of not permitting the bottom processor to be relabelled. Thus the expected behaviour of the k-state algorithm is bounded by the results given by the analysis of this sub-problem, which is shown to be \(O(n^{1.5})\) for the expected number of messages and \(O(n^ 2)\) for the expected number of rounds. The conclusion is that this distributed robustness algorithm which continuously monitors stability, is expensive to implement.