Back to Search
Start Over
Self-Stabilizing Mutual Exclusion Under Arbitrary Scheduler.
- Source :
- Computer Journal; 2004, Vol. 47 Issue 3, p289-298, 10p, 1 Diagram, 1 Chart
- Publication Year :
- 2004
-
Abstract
- 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(n³), 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00104620
- Volume :
- 47
- Issue :
- 3
- Database :
- Complementary Index
- Journal :
- Computer Journal
- Publication Type :
- Academic Journal
- Accession number :
- 15116065
- Full Text :
- https://doi.org/10.1093/comjnl/47.3.289