Token ring mutual exclusion

Distributed coordination

Distributed coordination means the techniques by which independent processes on different machines cooperate and synchronise their actions: mutual exclusion, election of a coordinator, agreement/consensus, ordering of events and multicast. There is no shared memory and no global clock, so coordination is done only by messages.

Token ring algorithm

This is a token-based mutual exclusion algorithm. A unique token gives the right to enter the critical section (CS).

Setup: processes are arranged in a logical ring P0, P1, ... Pn−1; each knows its successor. The token starts at P0.

Algorithm:

1. The token circulates around the ring in one direction, from Pi to P(i+1) mod n.
2. When a process receives the token:
   • If it wants the CS, it keeps the token, enters the CS, executes it and, on leaving, passes the token to its successor.
   • If it does not want the CS, it passes the token to the next process immediately.
3. A process may enter the CS only while holding the token, and only once per token visit.

        P0 ---token---> P1
        ^                |
        |                v
        P3 <----------- P2

Properties:

• Safety: there is only one token, so at most one process is in the CS.
• Liveness / fairness: each process gets the token within n−1 hops; no starvation.
• Messages: 1 to n−1 per CS entry; the token circulates even when nobody wants the CS (wasteful). Delay before entry: 0 to n−1 messages.

Problems and fixes:

• If the token is lost (a process crashes while holding it), the loss is hard to detect, because a long absence of the token may simply mean it is in use; a regeneration protocol with an election is needed.
• If a process crashes, the ring must be reconfigured (each process must know the successor after its neighbour; acknowledgements are used to detect crashes).