Maekawa's algorithm: Difference between revisions

Revision as of 13:26, 28 February 2006

Latest revision as of 12:53, 20 August 2025

(65 intermediate revisions by 42 users not shown)

Line 1:

'''Maekawa's Algorithmalgorithm''' is an algorithm for [[mutual exclusion]] on a [[distributed system]]. The basis of this algorithm is a [[quorum ]]-like approach where any one site needs only to seek permissions from a subset of other sites.

== Algorithm ==

== Algorithm ==

=== Terminology ===

* A ''site'' is any computing device which is runningruns the Ricart-AgrawalaMaekawa's Algorithmalgorithm

* For any one request of entering the [[critical section]]:

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

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

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

=== Algorithm ===

'''Requesting Sitesite''':

* A requesting site <math>P_i</math> sends a message <math>\text{request}(ts, i)</math> to all sites in its requestquorum siteset <math>R_i</math>.

'''Receiving Sitesite''':

* Upon reception of a <math>inquire\text{request}(jts, i)</math> message, the receiving site <math>P_kP_j</math> will:

'''Receiving Site''':

** UponIf receptionsite of<math>P_j</math> adoes not have an outstanding <math>request\text{grant}</math> message (tsthat is, i)a <math>\text{grant}</math> message, thethat receivinghas not been released), then site <math>P_j</math> will:sends a <math>\text{grant}(j)</math> message to site <math>P_i</math>.

** If site <math>P_j</math> does not havehas an outstanding <math>\text{grant}</math> message (that is,with a <math>grant</math>process messagewith thathigher haspriority notthan beenthe released)request, then site <math>P_j</math> sends a <math>grant\text{failed}(j)</math> message to site <math>P_i</math> and site <math>P_j</math> queues the request from site <math>P_i</math>.

** If site <math>P_j</math> has an outstanding <math>\text{grant}</math> message with a process with higherlower priority than the request, then site <math>P_j</math> sends aan <math>failed\text{inquire}(j)</math> message to sitethe <math>P_i</math>process andwhich has currently been granted access to the critical section by site <math>P_j</math>. queues(That is, the requestsite fromwith sitethe outstanding <math>P_i\text{grant}</math> message.)

* Upon reception of a <math>yield\text{inquire}(kj)</math> message, the site <math>P_jP_k</math> will:

** If site <math>P_j</math> has an outstanding <math>grant</math> message with a process with lower priority than the request, then site <math>P_j</math> sends an <math>inquire(j)</math> message to the process which has currently been granted access to the critical section by site <math>P_j</math>. (That is, the site with the outstanding <math>grant</math> message.)

** Send a <math>\text{yield}(k)</math> message to site <math>P_j</math> [[if and only if]] site <math>P_k</math> has received a <math>\text{failed}</math> message from some other site or if <math>P_k</math> has sent a yield to some other site but have not received a new <math>\text{grant}</math>.

* Upon reception of a <math>inquire(j)</math> message, the site <math>P_k</math> will:

* Upon reception of a <math>\text{yield}(k)</math> message, site <math>P_j</math> will:

** Send a <math>yield(k)</math> message to site <math>P_j</math> if and only if site <math>P_k</math> has received a <math>failed</math> message from some other site or if <math>P_k</math> has sent a yield to some other site but have not received a new <math>grant</math>.

** Send a <math>\text{grant}(j)</math> message to the request on the top of its own request queue. Note that the requests at the top are the highest priority.

* Upon reception of a <math>yield(k)</math> message, site <math>P_j</math> will:

** Send a <math>grant(j)</math> message to the request on the top of its own request queue.

** Place <math>P_k</math> into its request queue.

* Upon reception of a <math>\text{release}(i)</math> message, site <math>P_j</math> will:

** Delete <math>P_i</math> from its request queue.

** Send a <math>\text{grant}(j)</math> message to the request on the top of its request queue.

'''Critical Sectionsection''':

* Site <math>P_i</math> enters the critical section on recivingreceiving a <math>\text{grant}</math> message from all sites in <math>R_i</math>.

* Upon exiting the critical section, <math>P_i</math> sends a <math>\text{release}(i)</math> message to all sites in <math>R_i</math>.

'''Quorum Setset (<math>R_x</math>)''':<br />

'''Critical Section''':

* Site <math>P_i</math> enters the critical section on reciving a <math>grant</math> message from all sites in <math>R_i</math>.

* Upon exiting the critical section, <math>P_i</math> sends a <math>release(i)</math> message to all sites in <math>R_i</math>.

'''Quorum Set (<math>R_x</math>)''':<br />

A quorum set must abide by the following properties:

# <math>\forall i \,\forall j\, [R_i \bigcap R_j \ne \empty ]</math>

# <math>\forall i\, [ P_i \in R_i ]</math>

# <math>\forall i\, [ |R_i| = K ]</math>

# Site <math>P_i</math> is contained in exactly <math>K</math> request sets

:Therefore: <math>|R_i| \geq \sqrt{N-1}</math>

===Performance===

Therefore:

* Number of network messages; <math>|R_i|3 =\sqrt{N}</math> to <math>6 \sqrt{N}</math>

* Synchronization Delaysdelay: Two2 message propagation delaydelays

* The algorithm can deadlock without protections in place.<ref>{{Cite web|url=https://www.risc.jku.at/software/daj/Maekawa/|title=Maekawa's Mutual Exclusion Algorithm: Voting approach|last=|first=|date=|website=|access-date=}}</ref><ref>{{Cite web|url=https://www.cs.cmu.edu/~dga/15-440/F09/lectures/Distributed-Mutual-Exclusion-slides.pdf|title=Distributed Mutual Exclusion|last=|first=|date=|website=|access-date=}}</ref>

== See Also also==

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

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

* [[Ricart–Agrawala algorithm]]

* [[Raymond's Algorithmalgorithm]]

=== Performance =References==

{{Reflist}}

* Number of network messages; <math>3 \sqrt{N} - 5 \sqrt{N}</math>

* Synchronization Delays: Two message propagation delay

* M. Maekawa, "A √N algorithm for mutual exclusion in decentralized systems”, ACM

Transactions in Computer Systems, vol. 3., no. 2., pp. 145–159, 1985.

* Mamoru Maekawa, Arthur E. Oldehoeft, Rodney R. Oldehoeft (1987). Operating Systems: Advanced Concept. Benjamin/Cummings Publishing Company, Inc.

* B. Sanders (1987). The Information Structure of Distributed Mutual Exclusion Algorithms. ACM Transactions on Computer Systems, Vol. 3, No. 2, pp.&nbsp;145–59.

* [[{{DEFAULTSORT:Maekawa's Algorithm]]}}

== See Also ==

[[Category:Concurrency control algorithms]]

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

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

* [[Maekawa's Algorithm]]

* [[Suzuki-Kasami's Algorithm]]

* [[Raymond's Algorithm]]

[[Category:Algorithms]]