An algorithm for k-mutual exclusion in decentralized systems
The distributed k-mutual exclusion problem or, simply the k-mutex problem, is the problem of allowing at most k processes to access their critical sections simultaneously. This might be the consequence where k identical copies of a resource are made available in the distributed system or that the resource by its nature can be accessed by at most k processes simultaneously. When a process enters it critical section such that there are l < k processes in their critical sections, there is no interference of the mutual exclusion condition. In this paper, we present an algorithm for the k-mutex problem. The algorithm is token based and k tokens are used. A node may enter the critical section only if it possesses a token. The algorithm has a worst case message complexity of O(root n). Under heavy load the message requirement approaches 2 per critical section entry. The algorithm has been modified to enable fault tolerant capabilities. We have discussed node failure, message loss and link failure. (C) 2008 Elsevier B.V. All rights reserved.
k-mutual exclusion mutual exclusion distributed computing concurrency distributed algorithm