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.

• 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 ${\displaystyle P_{i}}${\displaystyle P_{i}} sends a message ${\displaystyle {\text{request}}(ts,i)}${\displaystyle {\text{request}}(ts,i)} to all sites in its quorum set ${\displaystyle R_{i}}${\displaystyle R_{i}}.

Receiving site:

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

Critical section:

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

Quorum set (${\displaystyle R_{x}}${\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 ]}${\displaystyle \forall i,円\forall j,円[R_{i}\bigcap R_{j}\neq \emptyset ]}
2. ${\displaystyle \forall i,円[P_{i}\in R_{i}]}${\displaystyle \forall i,円[P_{i}\in R_{i}]}
3. ${\displaystyle \forall i,円[|R_{i}|=K]}${\displaystyle \forall i,円[|R_{i}|=K]}
4. Site ${\displaystyle P_{i}}${\displaystyle P_{i}} is contained in exactly ${\displaystyle K}${\displaystyle K} request sets

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

• Number of network messages; ${\displaystyle 3{\sqrt {N}}}${\displaystyle 3{\sqrt {N}}} to ${\displaystyle 6{\sqrt {N}}}${\displaystyle 6{\sqrt {N}}}
• Synchronization delay: 2 message propagation delays
• The algorithm can deadlock without protections in place.^{[1] [2]}

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

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

• Concurrency control algorithms