- Ricart-Agrawala algorithm
The Ricart-Agrawala Algorithm is an algorithm for
mutual exclusion on adistributed system . This algorithm is an extension and optimization ofLamport's Distributed Mutual Exclusion Algorithm , by removing the need for messages. It was developed byGlenn Ricart andAshok Agrawala .Algorithm
Terminology
* A "site" is any computing device which is running the Ricart-Agrawala Algorithm
* The "requesting site" is the site which is requesting entry into the critical section.
* The "receiving site" is every other site which is receiving the request from the requesting site.Algorithm
Requesting Site:
* Sends a message to all sites. This message includes the site's name, and the current timestamp of the system according to itslogical clock ("which is assumed to be synchronized with the other sites")Receiving Site:
* Upon reception of a request message, immediately send a timestamped reply message if and only if::* the receiving process is not currently interested in the critical section OR:* the receiving process has a lower priority ("usually this means having a later timestamp)
* Otherwise, the receiving process will defer the reply message. This means that a reply will be sent only after the receiving process has finished using the critical section itself.Critical Section:
* Requesting site enters its critical section only after receiving all reply messages.
* Upon exiting the critical section, the site sends all deferred reply messages.Performance
* Number of network messages; 2*(N-1)
* Synchronization Delays: One message propagation delayCommon Optimizations
Once site has received a message from site , site may enter the critical section without receiving permission from until has sent a message to
This optimization is called Roucairol & Carvalho Optimization
Problems
One of the problems in this algorithm is failure of a node. In such a situation a process may starve forever.This problem can be solved by detecting failure of nodes after some timeout.
See also
* Lamport's Bakery Algorithm
*Lamport's Distributed Mutual Exclusion Algorithm
*Maekawa's Algorithm
*Suzuki-Kasami's Algorithm
*Raymond's Algorithm
*Naimi-Trehel's Algorithm
Wikimedia Foundation. 2010.