Ricart–Agrawala algorithm

The Ricart-Agrawala Algorithm is an algorithm for mutual exclusion on a distributed system. This algorithm is an extension and optimization of Lamport's Distributed Mutual Exclusion Algorithm, by removing the need for $release$ messages.

Algorithm

Terminology

• A site is any computing device which is running the Ricart-Agrawala Algorithm
• For any one request of the critical section:
  • 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.
• ts refers to the local timestamp of the system according to its Lamport clock.

Algorithm

Requesting Site:

• A requesting site $P_{i}$ sends a message $request(ts,i)$ to all sites.

Receiving Site:

• Upon reception of a $request(ts,i)$ message, the receiving site $P_{j}$ will immediately send a timestampped $reply(ts,j)$ message if and only if:
  • $P_{j}$ is not requesting or executing the critical section OR
  • $P_{j}$ is requesting the critical section but sent a request with a higher timestamp than the timestamp on $P_{j}$
• Otherwise, $P_{j}$ will defer the $reply$ message.

Critical Section:

• Site $P_{i}$ enters its critical section only after receiving all replies.
• Upon exiting the critical section, $P_{i}$ sends all deferred reply messages.

Performance

• Number of network messages; 2*(N-1)
• Synchronization Delays: One message propagation delay

Common Optimizations

Once site $P_{i}$ has received a $reply$ message from site $P_{j}$, site $P_{i}$ may enter the critical section without receiving permission from $P_{j}$ until $P_{i}$ has sent a $reply$ message to $P_{j}$

See Also

• Lamport's Distributed Mutual Exclusion Algorithm
• Maekawa's Algorithm
• Suzuki-Kasami's Algorithm
• Raymond's Algorithm