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{request}}(ts,i)$ to all sites in its quorum set $R_{i}$ .

Receiving site:

Upon reception of a ${\text{request}}(ts,i)$ message, the receiving site $P_{j}$ will:
- If site $P_{j}$ does not have an outstanding ${\text{grant}}$ message (that is, a ${\text{grant}}$ message that has not been released), then site $P_{j}$ sends a ${\text{grant}}(j)$ message to site $P_{i}$ .
- If site $P_{j}$ has an outstanding ${\text{grant}}$ message with a process with higher priority than the request, then site $P_{j}$ sends a ${\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 ${\text{grant}}$ message with a process with lower priority than the request, then site $P_{j}$ sends an ${\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 ${\text{grant}}$ message.)
Upon reception of a ${\text{inquire}}(j)$ message, the site $P_k$ will:
- Send a ${\text{yield}}(k)$ message to site $P_{j}$ if and only if site $P_k$ has received a ${\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 ${\text{grant}}$ .
Upon reception of a ${\text{yield}}(k)$ message, site $P_{j}$ will:
- Send a ${\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 ${\text{release}}(i)$ message, site $P_{j}$ will:
- Delete $P_{i}$ from its request queue.
- Send a ${\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 ${\text{grant}}$ message from all sites in $R_{i}$ .
Upon exiting the critical section, $P_{i}$ sends a ${\text{release}}(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\,[R_{i}\bigcap R_{j}\neq \emptyset ]$
$\forall i\,[P_{i}\in R_{i}]$
$\forall i\,[|R_{i}|=K]$
Site $P_{i}$ is contained in exactly $K$ request sets

Therefore:

$|R_{i}|\geq {\sqrt {N-1}}$

Performance

Number of network messages; $3{\sqrt {N}}$ to $6{\sqrt {N}}$
Synchronization delay: 2 message propagation delays

References

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.

This article is issued from Wikipedia - version of the 12/2/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Maekawa's algorithm

Algorithm

Terminology

Algorithm

Performance

See also

References