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. It was developed by Glenn Ricart and Ashok Agrawala.

Algorithm

Terminology

• A site is any computing device which is running ,
• 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.

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 multiple times without receiving permission from $P_{j}$ on subsequent attempts up to the moment when $P_{i}$ has sent a $reply$ message to $P_{j}$. 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 Distributed Mutual Exclusion Algorithm
• Maekawa's Algorithm
• Suzuki-Kasami's 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.