Consider a distributed system, consisting of N connected nodes, with no shared memory, that communicates by message passing. Many mutual-exclusion algorithms exist to coordinate the resource sharing of objects by these N nodes.
In centralized algorithms, nodes communicate their mutual-exclusion requests through one node, a coordinator node. This node takes these requests and grants critical section privileges. An advantage of these algorithms is that the number of messages passed per request is a constant value. A disadvantage is that the synchronization delay, the time interval after a node leaves a critical section, and before the next node enters the critical section, is two time units.
In token-based algorithms, mutual-exclusion is achieved by passing messages among the nodes. To execute in a critical section, a node broadcasts requests to all other nodes, making the number of messages passed per request N. Because there is no coordinator node, the synchronization delay is one unit.
In their note, the authors cleverly develop a centralized token-based mutual-exclusion algorithm that combines the best performance of the above algorithms. The coordinator’s supervisory role is trimmed. A critical-section request from some node is passed to the coordinator, but the coordinator forwards the requesting node number to the node granted access. When the node with the grant finishes, it passes the grant directly to the requesting node, reducing the synchronization delay time to one. Since no broadcasting is done, the number of messages per request is constant. The note also clearly describes the implementation of this algorithm.