|
Abstract : |
Self-stabilizing systems have been proposed as a desirable method of achieving fault tolerance. They are guaranteed to eventually eliminate any initial set of errors. This also implies that infrequent errors can be dealt with. For more details see [1-7]. In this paper we study deterministic self-stabilizing algorithms for leader election in rings. We have two sets of contributions. First, we introduce the formal definition of an observer at each location: a local process that can detect correctness, but cannot influence the protocol. Every self-stabilizing algorithm can have such associated observers. We believe that this is a good abstraction. We also claim that some such notion is necessary to make self-stabilizing protocols useful. The notion of an observer suggests a natural question to anyone familiar with the P vs. NP question: are there situations in which it is easier to detect stability than to achieve it? We exhibit a somewhat contrived problem where this is indeed the case. Our second contribution is a careful study of deterministic leader election algorithms on uniform rings of processors. We show that the class of protocols based on the general ideas of Burns and Pachl [2] require \Theta(n 3) steps in the worst case to become stable. We present a protocol for this problem that detects stability in \Theta(n 2) steps, and uses only five extra bits. Thus, for this class of algorithms verification is easier than computation. We also characterize exactly the memory requirements of these algorithms. The algorithm in [2] re0, |
