Multi-Token Distributed Mutual Exclusion Algorithm

This paper is a contribution to the inception of multiple tokens in solving distributed mutual exclusion problem. The proposed algorithm is based on the token ring approach and allows simultaneous existence of multiple tokens in the logical ring of the network. Each competing process generates a unique token and sends it as request to enter the critical section that travels along the ring. The process can only enter the critical section if it gets back its own token. The algorithm also handles the coincident existence of multiple critical sections (if any) in the system. The algorithm eliminates the idle time message passing, increases overall throughput and provides fault-tolerance. We discuss the impact of process failures and loss of tokens and propose corresponding recovery methods. The results of simulation show that the proposed algorithm overcomes the key limitations of the major token ring algorithms.