How Does Distributed Mutual Exclusion Work?
Learn distributed mutual exclusion — centralized, token-ring, and Ricart-Agrawala algorithms — with examples and interview questions.
Expected Interview Answer
Distributed mutual exclusion ensures that only one process across an entire network of machines enters a critical section at a time, achieved without shared memory through algorithms like centralized coordinators, token-passing rings, or Ricart-Agrawala's permission-based scheme using Lamport timestamps.
In a centralized approach, one node acts as coordinator and grants a lock via request/reply messages, which is simple but makes the coordinator a single point of failure and a bottleneck. In a token-ring approach, a single token circulates continuously among nodes in a logical ring, and only the node holding the token may enter its critical section, which guarantees fairness and freedom from starvation but wastes bandwidth circulating the token even when nobody needs it. The Ricart-Agrawala algorithm is fully distributed: a process wanting to enter its critical section timestamps its request with a Lamport clock and multicasts it to all other processes, then enters only after receiving a reply from every process, where replies are deferred by any process that is itself in or waiting for the critical section with an earlier timestamp. All three approaches must guarantee mutual exclusion, freedom from deadlock, and freedom from starvation, and they trade off message complexity (O(1) for centralized, O(n) for Ricart-Agrawala per entry, O(1) amortized for token ring) against fault tolerance and fairness.
- Guarantees exactly one critical-section holder with no shared memory
- Ricart-Agrawala avoids single points of failure via full multicast negotiation
- Token ring guarantees starvation-freedom through fixed-order circulation
- Underpins distributed locks, leader election, and resource allocation
AI Mentor Explanation
Distributed mutual exclusion is like several grounds sharing one traveling pitch-roller that only one groundskeeper can use at a time. A centralized scheme has a head groundskeeper hand out permission by phone; a token scheme has the roller physically travel a fixed circuit between grounds so whoever has it may use it; and a Ricart-Agrawala scheme has every groundskeeper text all the others a timestamped request and wait for every reply before rolling, deferring replies to anyone whose request timestamp is earlier.
Step-by-Step Explanation
Step 1
Request
A process wanting the critical section timestamps its request with a Lamport clock and sends it (to a coordinator, along the ring, or multicast to all peers).
Step 2
Arbitration
The chosen algorithm decides who goes first: the coordinator grants a lock, the token holder proceeds, or Ricart-Agrawala compares timestamps and defers replies accordingly.
Step 3
Enter critical section
Once granted (lock reply, token received, or all replies collected), the process safely enters its critical section.
Step 4
Release
The process releases the lock, passes the token onward, or sends deferred replies to waiting processes.
What Interviewer Expects
- Comparison of centralized, token-ring, and Ricart-Agrawala approaches
- Understanding of the request/reply defer logic tied to Lamport timestamps
- Awareness of trade-offs: single point of failure vs message overhead vs fairness
- Correctness properties: mutual exclusion, deadlock-freedom, starvation-freedom
Common Mistakes
- Assuming a distributed lock can use a simple shared-memory mutex
- Forgetting the coordinator is a single point of failure in the centralized scheme
- Not knowing Ricart-Agrawala requires replies from every other process
- Confusing distributed mutual exclusion with distributed deadlock detection
Best Answer (HR Friendly)
“Distributed mutual exclusion is about letting only one machine at a time do something sensitive, like updating a shared resource, when there is no shared memory to use a normal lock. Some approaches use a central coordinator to hand out permission, some pass a token around in a circle, and some have every machine ask every other machine and use timestamps to fairly decide who goes first.”
Code Example
struct request { long timestamp; int node_id; };
int wants_cs = 0;
long my_ts = 0;
struct request pending[MAX_NODES];
int pending_count = 0;
void request_cs(int my_id) {
wants_cs = 1;
my_ts = ++local_clock;
multicast_request(my_id, my_ts); /* send to all other nodes */
wait_for_all_replies(); /* block until n-1 replies arrive */
}
void on_incoming_request(int req_id, long req_ts) {
int defer = wants_cs &&
(my_ts < req_ts || (my_ts == req_ts && my_node_id < req_id));
if (defer) {
pending[pending_count++] = (struct request){ req_ts, req_id };
} else {
send_reply(req_id);
}
}Follow-up Questions
- What happens if the coordinator crashes in a centralized mutual exclusion scheme?
- How does the token-ring algorithm detect a lost token?
- Why does Ricart-Agrawala use node ID as a tiebreaker for equal timestamps?
- How does distributed mutual exclusion relate to distributed lock services like ZooKeeper?
MCQ Practice
1. In Ricart-Agrawala, when does a process defer replying to an incoming request?
A process defers its reply only if it is itself in the critical section or has a request with a timestamp that should be prioritized ahead of the incoming one.
2. What is the main weakness of the centralized mutual exclusion approach?
Since every request routes through one coordinator, its failure halts the whole system and it can become a performance bottleneck.
3. What guarantees starvation-freedom in the token-ring algorithm?
Because the token visits every node in a fixed cyclic order, every process is guaranteed to eventually receive it.
Flash Cards
What problem does distributed mutual exclusion solve? — Ensuring only one process across a network enters a critical section at a time, without shared memory.
Name three approaches. — Centralized coordinator, token-ring, and Ricart-Agrawala (timestamp-based multicast).
What is the weakness of a centralized scheme? — The coordinator is a single point of failure and a bottleneck.
How does Ricart-Agrawala decide priority? — By comparing Lamport timestamps, using node ID as a tiebreaker for equal timestamps.