Published by Dept. CS U. Chicago. Copyright 2002 CJTCS
Refining self-stabilizing algorithms which use tighter scheduling constraints (weaker daemon) into corresponding algorithms for weaker or no scheduling constraints (stronger daemon), while preserving the stabilization property, is useful and challenging. Designing transformation techniques for these refinements has been the subject of serious investigations in recent years. This paper proposes a new transformation technique for daemon refinement. The core of the transformer is a self-stabilizing local mutual exclusion algorithm. The local mutual exclusion problem is to grant a process the privilege to enter critical section if and only if none of its neighbors has the privilege. The contribution of this paper is twofold. First, we present a bounded-memory self-stabilizing local mutual exclusion algorithm for arbitrary networks, assuming any arbitrary daemon. After stabilization, this algorithm maintains a bound on the service time (the delay between two successive executions of critical section by a particular process). This bound is 0.5n(n-1) where n is the network size. Another nice feature of our algorithm is that it satisfies the strong safety property --- in any configuration, there is at least one privileged processor. Second, we use the local mutual exclusion algorithm to design two transformers which convert the algorithms working under a weaker daemon to ones which work under the distributed, arbitrary (or unfair) daemon. Both transformers preserve the self-stabilizing property. The first transformer refines algorithms written under the central daemon, while the second transformer refines algorithms designed for the k-fair (k >= (n-1)) daemon.