© 2004 by British Computer Society
Self-Stabilizing Mutual Exclusion Under Arbitrary Scheduler
1 School of Computer Science, Box 454019, University of Nevada-Las Vegas, Las Vegas, NV 89154-4019, USA 2 IRISA, Campus de Beaulieu, France 3 LRI-CNRS UMR 8623 & INRIA Futurs—Projet Grande Large, Université Paris Sud, France
A self-stabilizing algorithm, regardless of the initial system state, converges in finite time to a set of states that satisfy a legitimacy predicate. The mutual exclusion problem is fundamental in distributed computing, since it allows processors competing to access a shared resource to be able to synchronize and get exclusive access to the resource (i.e. execute their critical section). It is well known that providing self-stabilization in general uniform networks (e.g. anonymous rings of arbitrary size) can only be probabilistic. However, all existing uniform probabilistic self-stabilizing mutual exclusion algorithms designed to work under an unfair distributed scheduler (that may choose processors to execute their code in an arbitrary manner) suffer from the following common drawback: once stabilized, there exists no upper bound on time between two successive executions of the critical section at a given processor. In this paper, we present the first self-stabilizing algorithm that guarantees such a bound (O(n3), where n is the network size) while working using an unfair distributed scheduler. Our algorithm works in an anonymous unidirectional ring of any size and has a polynomial expected stabilization time.
Received 24 May 2002. Revised 17 October 2003.
* An extended version of the abstract of this paper appeared in the Proceedings of the 14th International Parallel & Distributed Processing Symposium, 2000.
Email: 
Email: