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.

Abstract We consider deterministic and randomized AC0 program checkers for standard P-complete and NC1-complete problems. Our focus is on the query complexity of the checker: i.e.\ the number of queries made by the checker to the program. We show that OMEGA(n^{1-\epsilon is a lower bound on the query complexity of deterministic AC0 checkers for these problems, for each epsilon>0, and inputs of length n. On the other hand, we design randomized AC0 checkers of constant query complexity for these problems.