Ricart–Agrawala algorithm: Difference between revisions

Revision as of 23:40, 27 February 2008

Latest revision as of 19:26, 15 November 2024

(56 intermediate revisions by 37 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.

{{more citations needed|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 release messages.<ref>{{cite journal|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

* ForThe any''requesting onesite'' requestis ofthe site which is requesting to enter the critical section:.

** The ''requestingreceiving site'' is theevery other site which is requestingreceiving entrya intorequest from the criticalrequesting sectionsite.

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

* ''ts'' refers to the local timestamp of the system according to its [[logical clock]].

=== 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'')

* A requesting site <math>P_i</math> sends a message <math>request(ts, i)</math> to all sites.

''' Receiving Site: '''

* Upon reception of a <math>request(ts, i)</math> message, the receiving site <math>P_j</math> will immediately sendsending a timestamped <math>''reply(ts, j)</math>'' message if and only if:

:** <math>P_j</math>the receiving process is not requestingcurrently orinterested executingin the critical section OR

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

** <math>P_j</math> is requesting the critical section but sent a request with a higher timestamp than the timestamp of <math>P_i</math>

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

''' Critical Section: '''

* SiteRequesting <math>P_i</math>site enters its critical section only after receiving all <math>reply</math> messages.

* Upon exiting the critical section, <math>P_i</math>the site sends all deferred <math>reply</math> 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}}

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