An Algorithm for Mutual Exclusion in Decentralized Systems

P. Chaudhuri and T. Edward (Barbados)


Computer network, mutual exclusion, distributed algorithm, message complexity.


In this paper a distributed algorithm is proposed that realises mutual exclusion among n nodes in a computer network. No common or global memory is 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 for distributed mutual exclusion achieves a message complexity of O(log N) per mutual exclusion invocation, where N log (N + 1) = n. It is also shown that the proposed algorithm performs better than the previously best known algorithm in [10] whose message complexity is O(n1/3 ).

Important Links:

Go Back