Maekawa's algorithm

• A site is any computing device which runs the Maekawa's algorithm
• 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

Requesting site:

• A requesting site $P\_i$ sends a message $\backslash text\{request\}(ts,\; i)$ to all sites in its quorum set $R\_i$.

Receiving site:

• Upon reception of a $\backslash text\{request\}(ts,\; i)$ message, the receiving site $P\_j$ will:
• If site $P\_j$ does not have an outstanding $\backslash text\{grant\}$ message (that is, a $\backslash text\{grant\}$ message that has not been released), then site $P\_j$ sends a $\backslash text\{grant\}(j)$ message to site $P\_i$.
• If site $P\_j$ has an outstanding $\backslash text\{grant\}$ message with a process with higher priority than the request, then site $P\_j$ sends a $\backslash text\{failed\}(j)$ message to site $P\_i$ and site $P\_j$ queues the request from site $P\_i$.
• If site $P\_j$ has an outstanding $\backslash text\{grant\}$ message with a process with lower priority than the request, then site $P\_j$ sends an $\backslash text\{inquire\}(j)$ message to the process which has currently been granted access to the critical section by site $P\_j$. (That is, the site with the outstanding $\backslash text\{grant\}$ message.)
• Upon reception of a $\backslash text\{inquire\}(j)$ message, the site $P\_k$ will:
• Send a $\backslash text\{yield\}(k)$ message to site $P\_j$ if and only if site $P\_k$ has received a $\backslash text\{failed\}$ message from some other site or if $P\_k$ has sent a yield to some other site but have not received a new $\backslash text\{grant\}$.
• Upon reception of a $\backslash text\{yield\}(k)$ message, site $P\_j$ will:
• Send a $\backslash 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.
• Place $P\_k$ into its request queue.
• Upon reception of a $\backslash text\{release\}(i)$ message, site $P\_j$ will:
• Delete $P\_i$ from its request queue.
• Send a $\backslash text\{grant\}(j)$ message to the request on the top of its request queue.

Critical section:

• Site $P\_i$ enters the critical section on receiving a $\backslash text\{grant\}$ message from all sites in $R\_i$.
• Upon exiting the critical section, $P\_i$ sends a $\backslash text\{release\}(i)$ message to all sites in $R\_i$.

Quorum set ($R\_x$):

A quorum set must abide by the following properties:

1. $\backslash forall\; i\; \backslash ,\backslash forall\; j\backslash ,\; [R\_i\; \backslash bigcap\; R\_j\; \backslash ne\; \backslash empty\; ]$
2. $\backslash forall\; i\backslash ,\; [\; P\_i\; \backslash in\; R\_i\; ]$
3. $\backslash forall\; i\backslash ,\; [\; |R\_i|\; =\; K\; ]$
4. Site $P\_i$ is contained in exactly $K$ request sets

:Therefore: $|R\_i|\; \backslash geq\; \backslash sqrt\{N-1\}$

• Number of network messages; $3\; \backslash sqrt\{N\}$ to $6\; \backslash sqrt\{N\}$
• Synchronization delay: 2 message propagation delays
• The algorithm can deadlock without protections in place.{{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=}}{{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=}}

• Lamport's bakery algorithm
• Lamport's Distributed Mutual Exclusion Algorithm
• Ricart–Agrawala algorithm
• Raymond's algorithm

{{Reflist}}

• 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. 145–59.

{{DEFAULTSORT:Maekawa's Algorithm}}

Category:Concurrency control algorithms