Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Maekawa's algorithm
open-in-new
<h2 id="algorithm">Algorithm</h2> <h3>Terminology</h3> <ul><li>A <i>site</i> is any computing device which runs the Maekawa's algorithm</li> <li>For any one request of entering the critical section: <ul><li>The <i>requesting site</i> is the site which is requesting to enter the critical section.</li> <li>The <i>receiving site</i> is every other site which is receiving the request from the requesting site.</li></ul></li> <li><i>ts</i> refers to the local time stamp of the system according to its <a href="/facts/Logical_clock/szv0m0lk">logical clock</a></li></ul> <h3>Algorithm</h3> <p>Requesting site: </p> <ul><li>A requesting site P i {\displaystyle P_{i}} sends a message request ( t s , i ) {\displaystyle {\text{request}}(ts,i)} to all sites in its quorum set R i {\displaystyle R_{i}} .</li></ul> <p>Receiving site: </p> <ul><li>Upon reception of a request ( t s , i ) {\displaystyle {\text{request}}(ts,i)} message, the receiving site P j {\displaystyle P_{j}} will: <ul><li>If site P j {\displaystyle P_{j}} does not have an outstanding grant {\displaystyle {\text{grant}}} message (that is, a grant {\displaystyle {\text{grant}}} message that has not been released), then site P j {\displaystyle P_{j}} sends a grant ( j ) {\displaystyle {\text{grant}}(j)} message to site P i {\displaystyle P_{i}} .</li> <li>If site P j {\displaystyle P_{j}} has an outstanding grant {\displaystyle {\text{grant}}} message with a process with higher priority than the request, then site P j {\displaystyle P_{j}} sends a failed ( j ) {\displaystyle {\text{failed}}(j)} message to site P i {\displaystyle P_{i}} and site P j {\displaystyle P_{j}} queues the request from site P i {\displaystyle P_{i}} .</li> <li>If site P j {\displaystyle P_{j}} has an outstanding grant {\displaystyle {\text{grant}}} message with a process with lower priority than the request, then site P j {\displaystyle P_{j}} sends an inquire ( j ) {\displaystyle {\text{inquire}}(j)} message to the process which has currently been granted access to the critical section by site P j {\displaystyle P_{j}} . (That is, the site with the outstanding grant {\displaystyle {\text{grant}}} message.)</li></ul></li> <li>Upon reception of a inquire ( j ) {\displaystyle {\text{inquire}}(j)} message, the site P k {\displaystyle P_{k}} will: <ul><li>Send a yield ( k ) {\displaystyle {\text{yield}}(k)} message to site P j {\displaystyle P_{j}} if and only if site P k {\displaystyle P_{k}} has received a failed {\displaystyle {\text{failed}}} message from some other site or if P k {\displaystyle P_{k}} has sent a yield to some other site but have not received a new grant {\displaystyle {\text{grant}}} .</li></ul></li> <li>Upon reception of a yield ( k ) {\displaystyle {\text{yield}}(k)} message, site P j {\displaystyle P_{j}} will: <ul><li>Send a grant ( j ) {\displaystyle {\text{grant}}(j)} message to the request on the top of its own request queue. Note that the requests at the top are the highest priority.</li> <li>Place P k {\displaystyle P_{k}} into its request queue.</li></ul></li> <li>Upon reception of a release ( i ) {\displaystyle {\text{release}}(i)} message, site P j {\displaystyle P_{j}} will: <ul><li>Delete P i {\displaystyle P_{i}} from its request queue.</li> <li>Send a grant ( j ) {\displaystyle {\text{grant}}(j)} message to the request on the top of its request queue.</li></ul></li></ul> <p>Critical section: </p> <ul><li>Site P i {\displaystyle P_{i}} enters the critical section on receiving a grant {\displaystyle {\text{grant}}} message from all sites in R i {\displaystyle R_{i}} .</li> <li>Upon exiting the critical section, P i {\displaystyle P_{i}} sends a release ( i ) {\displaystyle {\text{release}}(i)} message to all sites in R i {\displaystyle R_{i}} .</li></ul> <p>Quorum set ( R x {\displaystyle R_{x}} ): A quorum set must abide by the following properties: </p> <ol><li> ∀ i ∀ j [ R i ⋂ R j ≠ ∅ ] {\displaystyle \forall i\,\forall j\,[R_{i}\bigcap R_{j}\neq \emptyset ]} </li> <li> ∀ i [ P i ∈ R i ] {\displaystyle \forall i\,[P_{i}\in R_{i}]} </li> <li> ∀ i [ | R i | = K ] {\displaystyle \forall i\,[|R_{i}|=K]} </li> <li>Site P i {\displaystyle P_{i}} is contained in exactly K {\displaystyle K} request sets</li></ol> Therefore: <ul><li> | R i | ≥ N − 1 {\displaystyle |R_{i}|\geq {\sqrt {N-1}}} </li></ul> <h3>Performance</h3> <ul><li>Number of network messages; 3 N {\displaystyle 3{\sqrt {N}}} to 6 N {\displaystyle 6{\sqrt {N}}} </li> <li>Synchronization delay: 2 message propagation delays</li> <li>The algorithm can deadlock without protections in place.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a><a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a></li></ul> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Lamport%2527s_bakery_algorithm/LhNIQ02p">Lamport's bakery algorithm</a></li> <li><a href="/facts/Lamport%2527s_Distributed_Mutual_Exclusion_Algorithm/TkFhgM33">Lamport's Distributed Mutual Exclusion Algorithm</a></li> <li><a href="/facts/Ricart%25E2%2580%2593Agrawala_algorithm/hrK9KoVS">Ricart–Agrawala algorithm</a></li> <li><a href="/facts/Raymond%2527s_algorithm/zWQ0WpgN">Raymond's algorithm</a></li></ul> <ul><li>M. Maekawa, "A √N algorithm for mutual exclusion in decentralized systems”, ACM</li></ul> <p>Transactions in Computer Systems, vol. 3., no. 2., pp. 145–159, 1985. </p> <ul><li>Mamoru Maekawa, Arthur E. Oldehoeft, Rodney R. Oldehoeft (1987). Operating Systems: Advanced Concept. Benjamin/Cummings Publishing Company, Inc.</li> <li>B. Sanders (1987). The Information Structure of Distributed Mutual Exclusion Algorithms. ACM Transactions on Computer Systems, Vol. 3, No. 2, pp. 145–59.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>"Maekawa's Mutual Exclusion Algorithm: Voting approach". <a href="https://www.risc.jku.at/software/daj/Maekawa/" target="_blank">https://www.risc.jku.at/software/daj/Maekawa/</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>"Distributed Mutual Exclusion" (PDF). <a href="https://www.cs.cmu.edu/~dga/15-440/F09/lectures/Distributed-Mutual-Exclusion-slides.pdf" target="_blank">https://www.cs.cmu.edu/~dga/15-440/F09/lectures/Distributed-Mutual-Exclusion-slides.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> </ol>