The Ricart–Agrawala algorithm is an algorithm for
mutual exclusion
In computer science, mutual exclusion is a property of concurrency control, which is instituted for the purpose of preventing race conditions. It is the requirement that one thread of execution never enters a critical section while a concurr ...
on a
distributed system
Distributed computing is a field of computer science that studies distributed systems, defined as computer systems whose inter-communicating components are located on different networked computers.
The components of a distributed system commun ...
. This algorithm is an extension and optimization of
Lamport's Distributed Mutual Exclusion Algorithm, by removing the need for release messages.
It was developed by computer scientists
Glenn Ricart and
Ashok Agrawala.
Algorithm
Terminology
* A ''site'' is any computing device which runs the Ricart-Agrawala Algorithm
* The ''requesting site'' is the site which is requesting to enter the critical section.
* The ''receiving site'' is every other site which is receiving a 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 its
logical clock
A logical clock is a mechanism for capturing chronological and causal relationships in a distributed system. Often, distributed systems may have no physically synchronous global clock. In many applications (such as distributed GNU make), if two pro ...
(''which is assumed to be synchronized with the other sites'')
Receiving Site
* Upon reception of a request message, immediately sending 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
* Max number of network messages:
* Synchronization Delays: One message propagation delay
Common optimizations
Once site
has received a
message from site
, site
may enter the critical section multiple times without receiving permission from
on subsequent attempts up to the moment when
has sent a
message to
. This is called Roucairol-Carvalho optimization or Roucairol-Carvalho algorithm.
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 bakery algorithm is a computer algorithm devised by computer scientist Leslie Lamport, as part of his long study of the formal correctness of concurrent systems, which is intended to improve the safety in the usage of shared resource ...
*
Lamport's distributed mutual exclusion algorithm
*
Maekawa's algorithm Maekawa's algorithm is an algorithm for mutual exclusion on a distributed system. The basis of this algorithm is a quorum-like approach where any one site needs only to seek permissions from a subset of other sites.
Algorithm Terminology
* A ''si ...
*
Suzuki–Kasami algorithm
*
Raymond's algorithm
*
Naimi–Trehel's algorithm
References
*Maekawa, M., Oldehoeft, A., Oldehoeft, R.(1987). Operating Systems: Advanced Concept.Benjamin/Cummings Publishing Company, Inc.
{{DEFAULTSORT:Ricart-Agrawala Algorithm
Distributed algorithms