Ricart–Agrawala algorithm: Difference between revisions

Revision as of 10:45, 22 August 2019

Latest revision as of 19:26, 15 November 2024

(13 intermediate revisions by 10 users not shown)

Line 1:

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

{{refimprovemore 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>ack</math>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|urls2cid=https://dl.acm.org/citation.cfm?id=3585371779615|ref=origpaper|doi-access=free}}</ref>. It was developed by computer scientists [[Glenn Ricart]] and [[Ashok Agrawala]].

==Algorithm==

Line 24 ⟶ 25:

===Performance===

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

* Synchronization Delays: One message propagation delay

===Common Optimizationsoptimizations===

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

Line 35 ⟶ 36:

==See also==

* [[Lamport's bakery algorithm|Lamport's Bakery Algorithm]]

* [[Lamport's Distributeddistributed Mutualmutual Exclusionexclusion Algorithmalgorithm]]

* [[Maekawa's Algorithmalgorithm]]

* [[Suzuki-KasamiSuzuki–Kasami algorithm]]

* [[Raymond's Algorithmalgorithm]]

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

*[[Naimi-Trehel's Algorithm]]

==References==

{{RefListReflist}}

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

{{DEFAULTSORT:Ricart-Agrawala Algorithm}}