--- title: "Mutex requirements; token vs non-token" subject: "Distributed System" chapter: 6 key: "semester_7/distributed_system:mutex-requirements-compare" source: https://www.bctengineer.com/q/semester_7/distributed_system/mutex-requirements-compare site: BCT Engineering --- # Mutex requirements; token vs non-token Distributed System · Chapter 6: Coordination and Agreement - Asked in: 2072 Chaitra, 2+8 marks - Video: [DS11: Distributed System| Distributed Mutual Exclusion | Token based and non token based algo](https://www.youtube.com/watch?v=yduKTBqVAH8) — University Academy - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_7/distributed_system/mutex-requirements-compare - Whole chapter: https://www.bctengineer.com/md/semester_7/distributed_system/chapter-6 ## Question What are the basic requirements for mutual exclusion in distributed system? Explain the non-token based distributed mutual exclusion algorithm and compare it with token based algorithm. ## Short answer Requirements: safety (at most one in CS), liveness (no deadlock), fairness (no starvation), fault tolerance, low overhead. Non-token (Ricart-Agrawala): permission from all, 2(N-1) messages, timestamp ordering. Token-based: unique token circulates, 0 to N-1 messages, no starvation. Non-token has high overhead, token-based risks token loss. ## Answer #### Basic requirements for mutual exclusion 1. **Safety (mutual exclusion)**: at most one process is in the critical section (CS) at a time. 2. **Liveness (no deadlock)**: if requests are made, some process eventually enters; no process waits forever for messages. 3. **Fairness / no starvation**: every requesting process eventually enters, normally in the order in which requests were made (happened-before order). 4. **Fault tolerance**: the algorithm survives a failure of a process or loss of a message (desirable). 5. Low message overhead and small delay (performance). #### Non-token-based algorithm: Ricart-Agrawala Processes exchange timestamped messages to get permission; no token exists. 1. To enter, process Pi sends REQUEST(Ci, i) (Lamport timestamp) to all other N−1 processes. 2. A process Pj that gets a request replies immediately if it is neither in the CS nor wanting it, or if its own request has a larger timestamp. If it is in the CS, or wants it with an earlier timestamp, it defers the reply. 3. Pi enters the CS when it has received REPLY from all N−1 processes. 4. On leaving, Pi sends the deferred replies. Messages: 2(N−1) per entry; synchronisation delay: 1 message time. #### Comparison with token-based algorithms (e.g. token ring, Suzuki-Kasami) | Point | Non-token based | Token based | |---|---|---| | Permission | Obtained from other processes | Possession of the unique token | | Ordering | Timestamps | Token position/queue | | Messages per entry | 2(N−1) (high) | 0 to N−1 (ring) or N (broadcast) | | Safety | By agreement of all | By uniqueness of token | | Failure | A crashed process blocks; detectable by missing reply | Token can be lost; needs detection and regeneration | | Idle traffic | None | Token keeps circulating in ring | | Delay | Always a round of messages | Zero if holder wants CS again | | Starvation | None | None in ring | | Examples | Lamport, Ricart-Agrawala, Maekawa | Token ring, Suzuki-Kasami, Raymond | ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Which set lists the basic requirements for distributed mutual exclusion? A. Safety, liveness (no deadlock) and fairness (no starvation) B. Speed, memory and bandwidth C. Shared memory, global clock and a coordinator D. Replication, caching and consistency Answer: A. The core requirements are safety, liveness and fairness, with fault tolerance and low overhead desirable. (Key point: Requirements) 2. In Ricart-Agrawala, when does Pj defer its reply to a request? A. If it has the larger timestamp B. If it is in the CS, or wants it with an earlier timestamp C. If it is neither in the CS nor wanting it D. Always, until the token arrives Answer: B. A process in the CS or with an earlier pending request goes first, so it defers. (Key point: Non-token reply rule) 3. How do token-based and non-token-based algorithms differ in message behaviour? A. Token-based needs timestamps; non-token needs a token B. Non-token has zero delay if the holder wants the CS again C. Ring token circulates even when idle, while non-token has no idle traffic but 2(N-1) messages per entry D. Both have identical message cost Answer: C. Token ring keeps passing the token; non-token algorithms send messages only on request but need 2(N-1) per entry. (Key point: Token vs non-token idle traffic) 4. What is the typical failure problem in token-based algorithms? A. A missing reply is detected only after the token returns B. Timestamps become inconsistent C. Two tokens appear automatically D. The token can be lost and must be detected and regenerated Answer: D. Safety rests on the token's uniqueness, so losing it needs regeneration; non-token algorithms are blocked by crashed processes. (Key point: Failure mode) ## Related in Distributed System - [Token ring mutual exclusion](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Atoken-ring-mutex) — Distributed System, chapter 6, asked 3× - [Ricart-Agrawala mutual exclusion](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aricart-agrawala) — Distributed System, chapter 6, asked 2× - [Lamport algorithm for mutual exclusion](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Alamport-mutex) — Distributed System, chapter 6 - [Ways to achieve distributed mutex](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Amutex-methods) — Distributed System, chapter 6 - [Centralized vs Ricart-Agrawala algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Acentral-vs-ra-compare) — Distributed System, chapter 6 - [Autonomous vs distributed system](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aautonomous-vs-distributed) — Distributed System, chapter 1 ## Related in other subjects - [Race condition; mutual exclusion requirements](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Arace-mutual-exclusion-requirements) — Operating System, chapter 3 - [Critical section; mutual exclusion](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Acritical-section-mutual-exclusion-pc) — 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