• May 03, 2016 News! IJIET Vol. 5, No. 10 has been indexed by EI (Inspec).   [Click]
  • Mar 13, 2017 News!Vol. 7, No. 5 has been indexed by Crossref.
  • Mar 10, 2017 News!Vol. 7, No. 5 issue has been published online!   [Click]
General Information
    • ISSN: 2010-3689
    • Frequency: Bimonthly (2011-2014); Monthly (Since 2015)
    • DOI: 10.18178/IJIET
    • Editor-in-Chief: Prof. Dr. Steve Thatcher
    • Executive Editor: Ms. Nancy Y. Liu
    • Abstracting/ Indexing: EI (INSPEC, IET), Electronic Journals Library, Google Scholar, Crossref and ProQuest
    • E-mail: ijiet@ejournal.net
Prof. Dr. Steve Thatcher
University of South Australia, Australia
It is my honor to be the editor-in-chief of IJIET. The journal publishes good papers which focous on the advanced researches in the field of information and education technology. Hopefully, IJIET will become a recognized journal among the scholars in the filed of information and education technology.
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.


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.

Copyright © 2008-2016. International Journal of Information and Education Technology. All rights reserved.
E-mail: ijiet@ejournal.net