- 2072 Chaitra · 2+8 marks
Mutex requirements; token vs non-token
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.
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.
Basic requirements for mutual exclusion
- Safety (mutual exclusion): at most one process is in the critical section (CS) at a time.
- Liveness (no deadlock): if requests are made, some process eventually enters; no process waits forever for messages.
- Fairness / no starvation: every requesting process eventually enters, normally in the order in which requests were made (happened-before order).
- Fault tolerance: the algorithm survives a failure of a process or loss of a message (desirable).
- Low message overhead and small delay (performance).
Non-token-based algorithm: Ricart-Agrawala
Processes exchange timestamped messages to get permission; no token exists.
- To enter, process Pi sends REQUEST(Ci, i) (Lamport timestamp) to all other N−1 processes.
- 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.
- Pi enters the CS when it has received REPLY from all N−1 processes.
- 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 |
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Token ring mutual exclusion · Distributed System, chapter 6 · asked 3×
- Ricart-Agrawala mutual exclusion · Distributed System, chapter 6 · asked 2×
- Lamport algorithm for mutual exclusion · Distributed System, chapter 6
- Ways to achieve distributed mutex · Distributed System, chapter 6
- Centralized vs Ricart-Agrawala algorithm · Distributed System, chapter 6
- Autonomous vs distributed system · Distributed System, chapter 1
- Race condition; mutual exclusion requirements · Operating System, chapter 3
- Critical section; mutual exclusion · Operating System, chapter 3
- Semaphore for mutual exclusion · Operating System, chapter 3
- Mutual exclusion via sleep and wake · Embedded System, chapter 6