International Journal of
Information and Education Technology

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.