Ricart-Agrawala algorithm

The Ricart-Agrawala algorithm is an algorithm for mutual exclusion on a distributed system, developed by computer scientists Glenn Ricart and Ashok Agrawala. It extends and optimises Lamport's distributed mutual exclusion algorithm by removing the need for release messages. A site that wants to enter its critical section sends a request message to every other site, carrying its name and the current timestamp from its logical clock. A receiving site replies at once with a timestamped message if it is not interested in the critical section or if it has lower priority, which usually means a later timestamp. Otherwise it defers the reply until it has finished with the critical section itself. The requesting site enters the critical section only after receiving replies from all other sites, and on leaving it sends every deferred reply. Its synchronization delay is one message propagation delay. A common optimisation, the Roucairol-Carvalho optimisation, lets a site that already holds permission from another site re-enter the critical section repeatedly without asking again until it has replied to that site. A known weakness is that the failure of a node can make a process starve forever, which can be addressed by detecting failed nodes after a timeout.