--- title: "Ricart-Agrawala performance issues" subject: "Distributed System" chapter: 6 key: "semester_7/distributed_system:ra-performance-alternate" source: https://www.bctengineer.com/q/semester_7/distributed_system/ra-performance-alternate site: BCT Engineering --- # Ricart-Agrawala performance issues Distributed System · Chapter 6: Coordination and Agreement - Asked in: 2071 Shrawan, 2+6 marks - Video: [Ricart Agrawala Algorithm for Mutual Exclusion](https://www.youtube.com/watch?v=MUmCrwyzMCE) — Perfect Computer Engineer - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_7/distributed_system/ra-performance-alternate - Whole chapter: https://www.bctengineer.com/md/semester_7/distributed_system/chapter-6 ## Question Measure the performance issue of non-token based Ricart-Agrawala Algorithm. Write alternate algorithm to address those performance issues. ## Short answer Ricart-Agrawala requires 2(N-1) messages per entry, high overhead for large N, and any process crash blocks all. Maekawa's voting algorithm reduces messages to about 3√N by using intersecting quorums; a process needs permission only from its quorum members. Deadlock is possible but resolved with extra messages. ## Answer #### Performance of the Ricart-Agrawala algorithm Let N be the number of processes. - **Messages per CS entry**: N−1 requests and N−1 replies = 2(N−1). This grows linearly with N, which is heavy for large systems. - **Synchronisation delay**: one message time (after exit, the deferred reply reaches the waiting process). - **Response time** (low load): about one round trip, 2T, plus execution time. - **Failure sensitivity**: a request must be answered by all, so the crash of any one process blocks every other process; N points of failure instead of one. A crashed process can be treated as an implicit "no". - All processes must know the full membership and keep logical clocks. Thus the algorithm is correct but expensive and fragile. #### Alternate algorithm: Maekawa's voting algorithm Idea: a process needs permission from only a subset (quorum) of processes, not all. Quorums Ri for each Pi are chosen so that any two quorums intersect (Ri ∩ Rj ≠ ∅), each of size about √N, and each process is in about √N quorums. Algorithm: 1. To enter the CS, Pi sends REQUEST to every member of its quorum Ri. 2. A member votes (sends REPLY) for only one request at a time; if it has already voted, it queues the request (ordered by timestamp). 3. Pi enters the CS after receiving REPLY from all of Ri. 4. On exit, Pi sends RELEASE to all of Ri; each member then votes for the next queued request. Because any two quorums share at least one member, and that member votes for only one at a time, two processes cannot both enter. Performance: about **3√N messages** (request, reply, release), against 2(N−1) for Ricart-Agrawala. Deadlock is possible (circular vote waiting); it is solved by extra messages (INQUIRE, YIELD, FAILED) using timestamps. Another alternative is a token-based algorithm (Suzuki-Kasami: N messages, or Raymond's tree: O(log N)). ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What is the main performance problem of Ricart-Agrawala? A. 2(N-1) messages per entry, growing linearly with N B. Only 3 messages but a slow coordinator C. Token loss D. Needs no logical clocks Answer: A. N-1 requests plus N-1 replies makes the cost proportional to N. (Key point: RA message cost) 2. Why is Ricart-Agrawala fragile? A. It uses a single coordinator B. A reply is needed from all processes, so one crash blocks everyone C. The token may be lost D. It has no ordering of requests Answer: B. Because permission from every process is required, there are N points of failure. (Key point: Failure sensitivity) 3. What is the key idea of Maekawa's algorithm that reduces messages? A. Permission from a single coordinator B. Passing a token around the ring C. Permission is needed only from a quorum of about sqrt(N) processes, and any two quorums intersect D. Broadcasting to all and waiting for a majority Answer: C. Smaller intersecting quorums reduce messages to about 3 sqrt(N) while the common member ensures exclusion. (Key point: Maekawa quorums) 4. Why can two processes not both enter the CS in Maekawa's algorithm? A. Each process has a unique token B. Timestamps are globally synchronised C. The coordinator rejects the second one D. Two quorums share a member that votes for only one request at a time Answer: D. The shared quorum member gives its vote to one request at a time. (Key point: Why exclusion holds) ## Related in Distributed System - [Centralized vs Ricart-Agrawala algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Acentral-vs-ra-compare) — Distributed System, chapter 6 - [Ricart-Agrawala mutual exclusion](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aricart-agrawala) — Distributed System, chapter 6, asked 2× - [Mutex requirements; token vs non-token](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Amutex-requirements-compare) — Distributed System, chapter 6 ## 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× - [Issues modern configuration management must address](https://www.bctengineer.com/question.md?key=semester_5%2Fsoftware_engineering%3Asurvival-of-fittest) — Software Engineering, chapter 10 - [Unique vs non-unique address decoding](https://www.bctengineer.com/question.md?key=semester_5%2Finstrumentation_ii%3Aunique-vs-nonunique-decoding) — Instrumentation II, chapter 2