---
title: "Centralized vs Ricart-Agrawala algorithm"
subject: "Distributed System"
chapter: 6
key: "semester_7/distributed_system:central-vs-ra-compare"
source: https://www.bctengineer.com/q/semester_7/distributed_system/central-vs-ra-compare
site: BCT Engineering
---

# Centralized vs Ricart-Agrawala algorithm

Distributed System · Chapter 6: Coordination and Agreement

- Asked in: 2074 Asoj, 8 marks
- Video: [Ricart Agrawala Mutual Exclusion algorithm in Distributed Systems Synchronization](https://www.youtube.com/watch?v=EcoTlY0GXrA) — Simplified Computer Science Concepts-Prof. Rutuja
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_7/distributed_system/central-vs-ra-compare
- Whole chapter: https://www.bctengineer.com/md/semester_7/distributed_system/chapter-6

## Question

Describe non-token based centralized and Ricart Agrawala algorithm with example and compare them.

## 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.

## Answer

#### Centralized algorithm (non-token based)
One process is elected **coordinator**. It keeps a queue of requests.
1. A process wanting the critical section (CS) sends REQUEST to the coordinator.
2. If the CS is free, the coordinator sends GRANT (OK); otherwise it queues the request (or sends no reply).
3. The process enters the CS and, when done, sends RELEASE.
4. 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.
```text
 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 |

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. How many messages does the centralized algorithm use per CS entry, and which are they?
   A. 3: request, grant, release
   B. 2(N-1): requests and replies
   C. 3(N-1): request, reply, release
   D. N: broadcast and token
   Answer: A. The process sends REQUEST, the coordinator sends GRANT, and the process sends RELEASE. (Key point: Centralized messages)

2. In the centralized algorithm, what does the coordinator do when a request arrives while the CS is in use?
   A. Grants it at once
   B. Queues the request (or sends no reply) until the CS is released
   C. Forwards it to all other processes
   D. Rejects it permanently
   Answer: B. The coordinator keeps a queue and grants the next request after a RELEASE. (Key point: Coordinator behaviour)

3. Compare synchronisation delay (exit to next entry) of the two algorithms.
   A. Both need 1
   B. Centralized needs 1; Ricart-Agrawala needs 2
   C. Centralized needs 2 message times (release, then grant); Ricart-Agrawala needs 1
   D. Both need 2(N-1)
   Answer: C. In the centralized scheme the release goes to the coordinator then the grant goes out; in Ricart-Agrawala the deferred reply goes directly. (Key point: Synchronisation delay)

4. Which statement about failure is correct?
   A. Only the centralized algorithm has a single point of failure; Ricart-Agrawala tolerates any crash
   B. Neither is affected by crashes
   C. Ricart-Agrawala fails only if the coordinator crashes
   D. Centralized fails with the coordinator; Ricart-Agrawala is blocked by the crash of any process
   Answer: D. All replies are needed in Ricart-Agrawala, so any crash blocks everyone. (Key point: Failure comparison)

## Related in Distributed System

- [Ricart-Agrawala mutual exclusion](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aricart-agrawala) — Distributed System, chapter 6, asked 2×
- [Ricart-Agrawala performance issues](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Ara-performance-alternate) — Distributed System, chapter 6
- [Mutex requirements; token vs non-token](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Amutex-requirements-compare) — Distributed System, chapter 6
- [DS vs centralized; layers of transparency](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Ads-over-centralized-transparency) — Distributed System, chapter 1
- [Centralized vs distributed; design issues](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Acentralized-vs-distributed) — Distributed System, chapter 1
- [Token ring mutual exclusion](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Atoken-ring-mutex) — Distributed System, chapter 6, asked 3×

## Related in other subjects

- [Token bucket algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fcomputer_networks_and_security%3Atoken-bucket) — Computer Networks and Security, chapter 5, asked 4×
- [GA vs fuzzy based learning](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Aga-vs-fuzzy-learning) — Artificial Intelligence, chapter 6
- [Is recursion slow; recursive vs non-recursive](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Arecursion-slow-compare) — Data Structure and Algorithm, chapter 5