Semaphore and Monitor that protected critical section in single system are no longer appropriated in distributed systems. So in distributed systems, we must use a special algorithm to achieve mutual exclusion. There are 3 basic algorithms to be considered and work as a baseline for developing another mutual exclusion algorithm in distributed systems. Those 3 are:
- Centralized algorithm
- Distributed algorithm
- Token ring algorithm
Please refer to these articles for better understanding of mutual exclusion:
- Principle of Mutual Exclusion
- Semaphore: Mutual Exclusion in Single System
- Monitor: Mutual Exclusion in Single System
From the figure above, one node is elected as a coordinator. Coordinator is waiting for client request and issuing the token based on first come first serve. A token is an encrypted information that certify a particular node holding token to gain access to a shared resource. At a single time, only one node can hold the token. A node holding token will release token for other nodes whenever it does not need to access a shared resource anymore.
A cycle of token is (1) request token, (2) grant token, and (3) release token.
Advantages and Disadvantages
- First come first serve: it is fair and no process waits forever
- It is easy to implement
- It requires only 3 messages, request, grant, and release per use of a critical section