Maekawa's Algorithm

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

Algorithm

Requesting site:
* A requesting site $P_i$ sends a message $\text(ts, i)$ to all sites in its quorum set $R_i$.

Receiving site:
* Upon reception of a $\text(ts, i)$ message, the receiving site $P_j$ will:
** If site $P_j$ does not have an outstanding $\text$ message (that is, a $\text$ message that has not been released), then site $P_j$ sends a $\text(j)$ message to site $P_i$.
** If site $P_j$ has an outstanding $\text$ message with a process with higher priority than the request, then site $P_j$ sends a $\text(j)$ message to site $P_i$ and site $P_j$ queues the request from site $P_i$.
** If site $P_j$ has an outstanding $\text$ message with a process with lower priority than the request, then site $P_j$ sends an $\text(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 $\text$ message.)
* Upon reception of a $\text(j)$ message, the site $P_k$ will:
** Send a $\text(k)$ message to site $P_j$ if and only if site $P_k$ has received a $\text$ message from some other site or if $P_k$ has sent a yield to some other site but have not received a new $\text$.
* Upon reception of a $\text(k)$ message, site $P_j$ will:
** Send a $\text(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 $\text(i)$ message, site $P_j$ will:
** Delete $P_i$ from its request queue.
** Send a $\text(j)$ message to the request on the top of its request queue.

Critical section:
* Site $P_i$ enters the critical section on receiving a $\text$ message from all sites in $R_i$.
* Upon exiting the critical section, $P_i$ sends a $\text(i)$ message to all sites in $R_i$.

Quorum set ($R_x$):

A quorum set must abide by the following properties:
# \forall i \,\forall j\, _i \bigcap R_j \ne \empty /math>
# \forall i\, P_i \in R_i /math>
# \forall i\, R_i, = K /math>
# Site $P_i$ is contained in exactly $K$ request sets

:Therefore:
:* $, R_i, \geq \sqrt$

Performance

* Number of network messages; $3 \sqrt$ to $6 \sqrt$
* Synchronization delay: 2 message propagation delays
* The algorithm can deadlock without protections in place.

See also

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

References

* 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
Concurrency control algorithms