Ricart–Agrawala algorithm: Difference between revisions

Revision as of 19:05, 15 August 2009

Revision as of 08:36, 17 December 2009

Line 1:

{{Unreferenced|date=December 2009}}

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 <math>release</math> 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

Line 7 ⟶ 8:

* The ''receiving site'' is every other site which is receiving the request from the requesting site.

=== Algorithm ===

Requesting Site:

* Sends a message to all sites. This message includes the site's name, and the current timestamp of the system according to its [[logical clock]] (''which is assumed to be synchronized with the other sites'')

Line 21 ⟶ 22:

* Upon exiting the critical section, the site sends all deferred reply messages.

=== Performance ===

* Number of network messages; 2*(N-1)

* Synchronization Delays: One message propagation delay

=== Common Optimizations ===

Once site <math>P_i</math> has received a <math>reply</math> message from site <math>P_j</math>, site <math>P_i</math> may enter the critical section without receiving permission from <math>P_j</math> until <math>P_i</math> has sent a <math>reply</math> message to <math>P_j</math>

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 Bakery Algorithm]]

* [[Lamport's Distributed Mutual Exclusion Algorithm]]

Line 42 ⟶ 43:

*[[Naimi-Trehel's Algorithm]]

{{DEFAULTSORT:Ricart-Agrawala Algorithm}}

[[Category:Distributed algorithms]]

[[Category:Articles lacking sources (Erik9bot)]]

[[de:Ricart-Agrawala-Algorithmus]]