Ricart–Agrawala algorithm explained

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

ack

messages.[1] It was developed by computer scientists Glenn Ricart and Ashok Agrawala.

Algorithm

Terminology

Algorithm

Requesting Site

Receiving Site

Critical Section:

Performance

2*(N-1)

Common optimizations

Once site

Pi

has received a

reply

message from site

Pj

, site

Pi

may enter the critical section multiple times without receiving permission from

Pj

on subsequent attempts up to the moment when

Pi

has sent a

reply

message to

Pj

. 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

References

Notes and References

  1. Ricart. Glenn. Agrawala. Ashok K.. An optimal algorithm for mutual exclusion in computer networks. Communications of the ACM. 1 January 1981. 24. 1. 9–17. 10.1145/358527.358537. 1779615. origpaper. free.