Abstract
This thesis presents a new token-based K-mutual exclusion algorithm for distributed systems. The proposed algorithm uses K tokens to achieve K-mutual exclusion. The system of N nodes is organized as a logical forest, with the node possessing the token forming the root of a tree. For a system with K tokens, there are K such forests. The token with its associated token-queue and tag is passed among the nodes. Only nodes with a token are allowed to enter the Critical Section. Nodes that do not possess a token, send a request for the token along the edges of the forest. On receiving the token they enter the critical section. We show that the proposed algorithm achieves K-mutual exclusion and is free from deadlock and starvation. We analyze the algorithm at low and high rates of request for critical section execution. The simulation and implementation results show that the average number of messages and the average time to enter the critical section for our algorithm is small compared with other distributed K-mutual exclusion algorithms.
Bulgannawar, Shailaja Gurupad (1994). A distributed K-mutual exclusion algorithm. Master's thesis, Texas A&M University. Available electronically from
https : / /hdl .handle .net /1969 .1 /ETD -TAMU -1994 -THESIS -B933.