Ricart–Agrawala algorithm: Difference between revisions

Revision as of 19:05, 15 August 2009

Latest revision as of 19:26, 15 November 2024

(51 intermediate revisions by 34 users not shown)

Line 1:

{{Short description|Algorithm for mutual exclusion on a distributed system}}

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]].

{{more citations needed|date=December 2009}}

The '''Ricart-AgrawalaRicart–Agrawala Algorithmalgorithm''' 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 messages.</mathref>{{cite messagesjournal|last1=Ricart|first1=Glenn|last2=Agrawala|first2=Ashok K.|title=An optimal algorithm for mutual exclusion in computer networks|journal=Communications of the ACM|date=1 January 1981|volume=24|issue=1|pages=9–17|doi=10.1145/358527.358537|s2cid=1779615|ref=origpaper|doi-access=free}}</ref> It was developed by computer scientists [[Glenn Ricart]] and [[Ashok Agrawala]].

== Algorithm ==

== Algorithm ==

=== Terminology ===

* A ''site'' is any computing device which is runningruns the Ricart-Agrawala Algorithm

* The ''requesting site'' is the site which is requesting entryto intoenter the critical section.

* The ''receiving site'' is every other site which is receiving thea 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'')

''' Receiving Site: '''

* Upon reception of a request message, immediately sendsending a timestamped ''reply'' message if and only if:

:* the receiving process is not currently interested in the critical section OR

:* the receiving process has a lower priority (''usually this means having a later timestamp)

* Otherwise, the receiving process will defer the reply message. This means that a reply will be sent only after the receiving process has finished using the critical section itself.

''' Critical Section: '''

* Requesting site enters its critical section only after receiving all reply messages.

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

=== Performance ===

* NumberMax number of network messages;: <math>2*(N-1)</math>

* Synchronization Delays: One message propagation delay

=== Common Optimizations 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 multiple times without receiving permission from <math>P_j</math> untilon subsequent attempts up to the moment when <math>P_i</math> has sent a <math>reply</math> message to <math>P_j</math>. This is called Roucairol-Carvalho optimization or Roucairol-Carvalho algorithm.

=== Problems ===

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 Distributeddistributed Mutualmutual Exclusionexclusion Algorithmalgorithm]]

* [[Maekawa's Algorithmalgorithm]]

* [[Suzuki-Kasami'sSuzuki–Kasami Algorithmalgorithm]]

* [[Raymond's Algorithmalgorithm]]

* [[Naimi–Trehel algorithm|Naimi–Trehel's algorithm]]

*[[Naimi-Trehel's Algorithm]]

==References==

[[Category:Distributed algorithms]]

{{Reflist}}

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

*Maekawa, M., Oldehoeft, A., Oldehoeft, R.(1987). Operating Systems: Advanced Concept.Benjamin/Cummings Publishing Company, Inc.

[[de{{DEFAULTSORT:Ricart-Agrawala-Algorithmus]] Algorithm}}

[[Category:Distributed algorithms]]