- 2074 Asoj · 8 marks
Centralized vs Ricart-Agrawala algorithm
Short answer
Centralized: coordinator grants CS; 3 messages per entry, single point of failure. Ricart-Agrawala: fully distributed, 2(N-1) messages, uses timestamps, any process crash blocks all. Centralized is simpler, scalable until coordinator saturates; RA has no bottleneck but high overhead for large N. Example: centralized: P1 requests, coordinator grants; P2 queued. RA: P1 and P2 request, P1 wins by timestamp.
Describe non-token based centralized and Ricart Agrawala algorithm with example and compare them.
Centralized algorithm (non-token based)
One process is elected coordinator. It keeps a queue of requests.
- A process wanting the critical section (CS) sends REQUEST to the coordinator.
- If the CS is free, the coordinator sends GRANT (OK); otherwise it queues the request (or sends no reply).
- The process enters the CS and, when done, sends RELEASE.
- The coordinator removes the next request from its queue and grants it.
Example: P1 asks; coordinator C grants. P2 asks; C queues it. P1 releases; C grants to P2.
P1 --REQ--> C --OK--> P1 (in CS)
P2 --REQ--> C (queued)
P1 --REL--> C --OK--> P2
Messages per entry: 3 (request, grant, release).
Ricart-Agrawala algorithm
Fully distributed, uses Lamport timestamps. To enter the CS, a process multicasts REQUEST(timestamp, id) to all N−1 others and enters when it has received REPLY from all. A receiver replies immediately if it is not interested in the CS or its own request has a larger timestamp; it defers the reply if it is in the CS or has a smaller timestamp request. On exit, deferred replies are sent.
Example: P1 (timestamp 4) and P2 (timestamp 5) request together; P1 wins since 4 < 5; P2 gets its reply after P1 finishes. Messages per entry: 2(N−1).
Comparison
| Point | Centralized | Ricart-Agrawala |
|---|---|---|
| Control | One coordinator | Fully distributed |
| Messages per entry | 3 | 2(N−1) |
| Delay before entry | 2 message times | 2 message times (one round trip) |
| Synchronisation delay | 2 (release then grant) | 1 |
| Single point of failure | Yes: coordinator crash | Yes: any process crash blocks everyone |
| Bottleneck | Coordinator | None, but every node loaded |
| Fairness | Queue order (FIFO) | Timestamp order |
| Clock needed | No | Yes, logical clocks |
| Simplicity | Simple | More complex |
| Scalability | Good until coordinator saturates | Poor as N grows |
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Ricart-Agrawala mutual exclusion · Distributed System, chapter 6 · asked 2×
- Ricart-Agrawala performance issues · Distributed System, chapter 6
- Mutex requirements; token vs non-token · Distributed System, chapter 6
- DS vs centralized; layers of transparency · Distributed System, chapter 1
- Centralized vs distributed; design issues · Distributed System, chapter 1
- Token ring mutual exclusion · Distributed System, chapter 6 · asked 3×
- Token bucket algorithm · Computer Networks and Security, chapter 5 · asked 4×
- GA vs fuzzy based learning · Artificial Intelligence, chapter 6
- Is recursion slow; recursive vs non-recursive · Data Structure and Algorithm, chapter 5