Observing Self-Stabilization

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. ..