Maekawa's algorithm: Difference between revisions

Revision as of 11:35, 16 January 2017

Latest revision as of 12:53, 20 August 2025

(15 intermediate revisions by 8 users not shown)

Line 1:

'''Maekawa's algorithm''' 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.

{{Unreferenced|date=December 2009}}

'''Maekawa's algorithm''' 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==

=== Terminology ===

* A ''site'' is any computing device which runs the Maekawa's Algorithmalgorithm

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

** The ''requesting site'' is the site which is requesting to enter the critical section.

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

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

===Algorithm===

Line 20 ⟶ 19:

** If site <math>P_j</math> has an outstanding <math>\text{grant}</math> message with a process with lower priority than the request, then site <math>P_j</math> sends an <math>\text{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>\text{grant}</math> message.)

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

** 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>\text{yield}(k)</math> message, site <math>P_j</math> will:

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

Line 39 ⟶ 38:

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

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

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

===Performance===

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

* Synchronization delay: 2 message propagation delays

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

* [[Lamport's bakery algorithm]]

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

* [[Ricart-AgrawalaRicart–Agrawala algorithm]]

* [[Raymond's algorithm]]

==References==

{{Reflist}}

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

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