JUCS - Journal of Universal Computer Science 12(2): 140-159, doi: 10.3217/jucs-012-02-0140
An O(√n) Distributed Mutual Exclusion Algorithm Using Queue Migration
expand article infoPranay Chaudhuri‡, Thomas Edward‡
‡ University of the West Indies, Cave Hill Campus, Barbados

Corresponding author: Pranay Chaudhuri ( pchaudhuri@uwichill.edu.bb )

© Pranay Chaudhuri, Thomas Edward.
This article is freely available under the J.UCS Open Content License.
Citation: Chaudhuri P, Edward T (2006) An O(√n) Distributed Mutual Exclusion Algorithm Using Queue Migration. JUCS - Journal of Universal Computer Science 12(2): 140-159. https://doi.org/10.3217/jucs-012-02-0140
Open Access
Abstract
In this paper a distributed algorithm is proposed that realises mutual exclusion among n nodes in a computer network. There is no common or global memory shared by the nodes and there is no global controller. The nodes of the network communicate among themselves by exchanging messages only. The proposed algorithm is based on queue migration and achieves a message complexity of O(√n) per mutual exclusion invocation. Under heavy load, the number of required messages approaches 2 per mutual exclusion.
Keywords
mutual exclusion, critical section, distributed algorithm, computer network, queue migration, message complexity