Chicago Journal of Theoretical Computer Science

Volume 2002

Article 1

Published by Dept. CS U. Chicago. Copyright 2002 CJTCS

Self-Stabilizing Local Mutual Exclusion and Daemon Refinement

Joffroy Beauquier (Universite' de Paris Sud), Ajoy K. Datta (University of Nevada Las Vegas) Maria Gradinariu and Frederic Magniette (Universite' de Paris Sud)
24 July 2002

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.

DOI: 10.4086/cjtcs.2002.001
[] Volume 2000, Article 4 [] Article 2
[back] Volume 2002 [back] Published articles
[CJCTS home]