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 is running the Maekawaa's Algorithm
• For any one request of the critical section:
  • The requesting site is the site which is requesting entry into the critical section.
  • The receiving site is every other site which is receiving the request from the requesting site.
• ts refers to the local timestamp of the system according to its logical clock.

Algorithm

Requesting site:

• A requesting site ${\displaystyle P_{i}}$  sends a message ${\displaystyle {\text{request}}(ts,i)}$  to all sites in its quorum set ${\displaystyle R_{i}}$ .

Receiving site:

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

Critical section:

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

Quorum set (${\displaystyle R_{x}}$ ):
A quorum set must abide by the following properties:

1. ${\displaystyle \forall i\,\forall j\,[R_{i}\bigcap R_{j}\neq \emptyset ]}$ 
2. ${\displaystyle \forall i\,[P_{i}\in R_{i}]}$ 
3. ${\displaystyle \forall i\,[|R_{i}|=K]}$ 
4. Site ${\displaystyle P_{i}}$  is contained in exactly ${\displaystyle K}$  request sets

Therefore:

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

Performance

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

See also

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

References

Maekawa, M.,Oldehoeft, A.,Oldehoeft, R.(1987). Operating Systems: Advanced Concept.Benjamin/Cummings Publishing Company, Inc.
Saunders, B. (1987). The Information Structure of Distributed Mutual Exclusion Algorithms. ACM Transactions on Computer Systems, Vol. 3, No. 2, pp. 145–59