On the costs of self-stabilization (Q1098276)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the costs of self-stabilization |
scientific article |
Statements
On the costs of self-stabilization (English)
0 references
1987
0 references
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.
0 references
distributed system
0 references
Concurrent programming
0 references
analysis of algorithms
0 references
reliability
0 references
Dijkstra recovery algorithms
0 references
self-stabilization
0 references
labellings
0 references