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.