--- title: "Token ring mutual exclusion" subject: "Distributed System" chapter: 6 key: "semester_7/distributed_system:token-ring-mutex" source: https://www.bctengineer.com/q/semester_7/distributed_system/token-ring-mutex site: BCT Engineering --- # Token ring mutual exclusion Distributed System · Chapter 6: Coordination and Agreement - Asked in: 2073 Shrawan, 2+6 marks; 2071 Chaitra, 10 marks; 2075 Chaitra, 2+6 marks (asked 3 times) - Video: [Mutual Exclusion in DS- Token Ring Algorithm -Part 3](https://www.youtube.com/watch?v=KSBVEAKfKus) — Norman Dias - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_7/distributed_system/token-ring-mutex - Whole chapter: https://www.bctengineer.com/md/semester_7/distributed_system/chapter-6 ## Question Define distributed coordination in DS. Explain with algorithmic steps how token ring (token based) algorithm works for mutual exclusion in distributed system. ## Short answer Distributed coordination enables independent processes to synchronize via messages. In token ring, processes form a logical ring; a unique token circulates. A process wanting the critical section holds the token, enters CS, then passes it on. If not interested, it forwards immediately. Safety: only one token ensures mutual exclusion; fairness: token visits each process. ## Answer #### 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. ```text 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). ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. In the token ring mutual exclusion algorithm, when does a process enter its critical section? A. Only while it holds the token, and only once per token visit B. Whenever it has sent a request to its successor C. When it has received replies from all other processes D. Whenever the token is anywhere in the ring and it has the smallest id Answer: A. The token gives the right to enter the CS. A process holding it may enter once, then must pass it on. (Key point: Token ring rule) 2. Why does the token ring algorithm guarantee that at most one process is in the critical section? A. Every process votes on who may enter B. There is only one unique token and only its holder may enter C. Timestamps order all the requests D. A coordinator grants permission to one process Answer: B. Safety comes from the uniqueness of the token, not from voting, timestamps or a coordinator. (Key point: Safety) 3. Which is a drawback of the token ring algorithm? A. It needs 2(N-1) messages per entry B. It needs synchronised physical clocks C. The token keeps circulating even when no process wants the CS, wasting messages D. It can starve a process indefinitely Answer: C. The token moves around continuously, so messages are used even when nobody wants the CS. Each process gets the token within n-1 hops, so no starvation. (Key point: Cost of token ring) 4. What is the difficulty if the process holding the token crashes? A. The other processes all enter the CS together B. The ring automatically restores the token at once C. The successor is always sure the token is lost D. The loss is hard to detect (the token may merely be in use) and needs regeneration with an election Answer: D. Silence of the token may mean it is in use, so detecting loss is hard; a regeneration protocol with an election is needed. (Key point: Token loss) ## Related in Distributed System - [Lamport algorithm for mutual exclusion](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Alamport-mutex) — Distributed System, chapter 6 - [Ricart-Agrawala mutual exclusion](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aricart-agrawala) — Distributed System, chapter 6, asked 2× - [Mutex requirements; token vs non-token](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Amutex-requirements-compare) — Distributed System, chapter 6 - [Bully algorithm vs ring algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aelection-bully-ring) — Distributed System, chapter 6 - [DS as a single coherent system](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Asingle-coherent-system) — Distributed System, chapter 1, asked 2× - [Ways to achieve distributed mutex](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Amutex-methods) — Distributed System, chapter 6 ## Related in other subjects - [Critical section; mutual exclusion](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Acritical-section-mutual-exclusion-pc) — Operating System, chapter 3 - [Race condition; mutual exclusion requirements](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Arace-mutual-exclusion-requirements) — Operating System, chapter 3 - [Semaphore for mutual exclusion](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Asemaphore-enforce-mutual-exclusion) — Operating System, chapter 3 - [Mutual exclusion via sleep and wake](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Amutual-exclusion-sleep-wake) — Embedded System, chapter 6