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 ${\displaystyle release}$ messages. It was developed by Glenn Ricart and Ashok Agrawala.

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 logical clock.

Algorithm

Requesting Site:

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

Receiving Site:

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

Critical Section:

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

Performance

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

Common Optimizations

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

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