Home > Archive > 2013 > Volume 3 Number 3 (Jun. 2013) >
IJIET 2013 Vol.3(3): 353-357 ISSN: 2010-3689
DOI: 10.7763/IJIET.2013.V3.296

A Self-Stabilizing Algorithm for the Generalization of the Mutual Exclusion Problem

Mehmet Hakan Karaata and Rachid Hadid

Abstract—In this paper, we present the first stabilizing solution to the ℓ-exclusion problem in arbitrary networks. The ℓ-exclusion problem is a generalization of the mutual exclusion problem to ℓ (ℓ ≥ 1) processes, instead of 1, are free to use a shared resource simultaneously. The algorithm is semi-uniform and its space requirement is (ℓ + 3)Δr states for the root r, 4 × Δ2p × Lmax states for each non root process p, where Δp is the degree of process p and Lmax is the diameter of the communication network. This is the first ℓ-exclusion algorithm on arbitrary networks with the property that the space requirement is independent of ℓ for all processes except the root. The proposed protocol is distributed, deterministic, and does not use a pre-constructed spanning tree. Since our algorithm is self-stabilizing, it does not require initialization and withstands transient faults. The stabilization time of the algorithm is O(⌈n/l⌉ × (ℓ + Lmax)) rounds.

Index Terms—Distributed systems, fault-tolerance, self-stabilization, ℓ-exclusion, propagation of information with feedback.

Mehmet Hakan Karaata is with Department of Computer Scienc e and Department of Computer Eng P.O. Box 5969, Safat 13060 Kuwait (e-mail: karaata@gmail.com).
Rachid Hadid is with MIS, Universite ́ de Picardie Jules Verne , 33, rue Saint Leu, 80039 Amiens Cedex 01, France.

[PDF]

Cite:Mehmet Hakan Karaata and Rachid Hadid, "A Self-Stabilizing Algorithm for the Generalization of the Mutual Exclusion Problem," International Journal of Information and Education Technology vol. 3, no. 3, pp. 353-357, 2013.

General Information

  • ISSN: 2010-3689 (Online)
  • Abbreviated Title: Int. J. Inf. Educ. Technol.
  • Frequency: Monthly
  • DOI: 10.18178/IJIET
  • Editor-in-Chief: Prof. Dr. Steve Thatcher
  • Managing Editor: Ms. Nancy Y. Liu
  • Abstracting/ Indexing: Scopus (CiteScore 2022: 2.0), INSPEC (IET), UGC-CARE List (India), CNKI, EBSCO, Google Scholar
  • E-mail: ijiet@ejournal.net

 

Article Metrics in Dimensions