Special Issue – Advances in Parallel and Distributed Computational Models (APDCM 2009)No Access

SELF-STABILIZING k-out-of-ℓ EXCLUSION IN TREE NETWORKS

AJOY K. DATTA

School of Computer Science, University of Nevada, Las Vegas, USA

Search for more papers by this author

STÉPHANE DEVISMES

VERIMAG, Université Joseph Fourier, Grenoble, France

Search for more papers by this author

FLORIAN HORN

LIAFA, Université Paris Denis Diderot, Paris, France

Search for more papers by this author

, and

LAWRENCE L. LARMORE

School of Computer Science, University of Nevada, Las Vegas, USA

Search for more papers by this author

https://doi.org/10.1142/S0129054111008283Cited by:2 (Source: Crossref)

Abstract

In this paper, we address the problem of k-out-of-ℓ exclusion, a generalization of the mutual exclusion problem, in which there are ℓ units of a shared resource, and any process can request up to k units (1 ≤ k ≤ ℓ). A protocol is self-stabilizing if, starting from an arbitrary configuration, be it initial state or after a corrupted state, the protocol can start behaving normally within a finite time. We propose the first deterministic self-stabilizing distributed k-out-of-ℓ exclusion protocol in message-passing systems for asynchronous oriented tree networks which assumes bounded local memory for each process.

Keywords:

AMSC: 68Q22, 68M15

References

A. K. Datta, R. Hadid and V. Villain, Self-Stabilizing Systems, Lecture Notes in Computer Science 2704, eds. Shing-Tsaan Huang and Ted Herman (Springer, 2003) pp. 113–128. Crossref, Google Scholar
A. K. Datta, R. Hadid and V. Villain, Concurrency and Computation: Practice and Experience 15(11-12), 1069 (2003), DOI: 10.1002/cpe.781. Crossref, Web of Science, Google Scholar
E. W. Dijkstra, Communications of the Association of the Computing Machinery 17, 643 (1974). Crossref, Web of Science, Google Scholar
Shlomi Dolev , Self-Stabilization ( The MIT Press , 2000 ) . Crossref, Google Scholar
M. J. Fischeret al., ACM Trans. Program. Lang. Syst. 11(1), 90 (1989), DOI: 10.1145/59287.59292. Crossref, Web of Science, Google Scholar
Mohamed G. Gouda and Nicholas J. Multari, IEEE Trans. Computers 40(4), 448 (1991), DOI: 10.1109/12.88464. Crossref, Web of Science, Google Scholar
Rachid Hadid and Vincent Villain, A new efficient tool for the design of self-stabilizing l-exclusion algorithms: The controller, WSS2194, Lecture Notes in Computer Science, eds. Ajoy Kumar Datta and Ted Herman (Springer, 2001) pp. 136–151. Google Scholar
Shmuel Katz and Kenneth J. Perry, Distributed Computing 7(1), 17 (1993), DOI: 10.1007/BF02278852. Crossref, Web of Science, Google Scholar
Y. Manabeet al., Theor. Comput. Sci. 193(1-2), 97 (1998), DOI: 10.1016/S0304-3975(97)00303-4. Crossref, Web of Science, Google Scholar
Y. Manabe and N. Tajima, (k)-arbiter for h-out of-k mutual exclusion problem, ICDCS (1999) pp. 216–223. Google Scholar
M. Raynal, A distributed solution to the k-out of-m resources allocation problem, ICCI497, Lecture Notes in Computer Science, eds. F. K. H. A. Dehne, F. Fiala and W. W. Koczkodaj (Springer, 1991) pp. 599–609. Google Scholar
George Varghese, SIAM J. Comput. 30(2), 486 (2000), DOI: 10.1137/S009753979732760X. Crossref, Web of Science, Google Scholar