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 [math]\displaystyle{ P_i }[/math] sends a message [math]\displaystyle{ \text{request}(ts, i) }[/math] to all sites in its quorum set [math]\displaystyle{ R_i }[/math].

Receiving site:

• Upon reception of a [math]\displaystyle{ \text{request}(ts, i) }[/math] message, the receiving site [math]\displaystyle{ P_j }[/math] will:
  • If site [math]\displaystyle{ P_j }[/math] does not have an outstanding [math]\displaystyle{ \text{grant} }[/math] message (that is, a [math]\displaystyle{ \text{grant} }[/math] message that has not been released), then site [math]\displaystyle{ P_j }[/math] sends a [math]\displaystyle{ \text{grant}(j) }[/math] message to site [math]\displaystyle{ P_i }[/math].
  • If site [math]\displaystyle{ P_j }[/math] has an outstanding [math]\displaystyle{ \text{grant} }[/math] message with a process with higher priority than the request, then site [math]\displaystyle{ P_j }[/math] sends a [math]\displaystyle{ \text{failed}(j) }[/math] message to site [math]\displaystyle{ P_i }[/math] and site [math]\displaystyle{ P_j }[/math] queues the request from site [math]\displaystyle{ P_i }[/math].
  • If site [math]\displaystyle{ P_j }[/math] has an outstanding [math]\displaystyle{ \text{grant} }[/math] message with a process with lower priority than the request, then site [math]\displaystyle{ P_j }[/math] sends an [math]\displaystyle{ \text{inquire}(j) }[/math] message to the process which has currently been granted access to the critical section by site [math]\displaystyle{ P_j }[/math]. (That is, the site with the outstanding [math]\displaystyle{ \text{grant} }[/math] message.)
• Upon reception of a [math]\displaystyle{ \text{inquire}(j) }[/math] message, the site [math]\displaystyle{ P_k }[/math] will:
  • Send a [math]\displaystyle{ \text{yield}(k) }[/math] message to site [math]\displaystyle{ P_j }[/math] if and only if site [math]\displaystyle{ P_k }[/math] has received a [math]\displaystyle{ \text{failed} }[/math] message from some other site or if [math]\displaystyle{ P_k }[/math] has sent a yield to some other site but have not received a new [math]\displaystyle{ \text{grant} }[/math].
• Upon reception of a [math]\displaystyle{ \text{yield}(k) }[/math] message, site [math]\displaystyle{ P_j }[/math] will:
  • Send a [math]\displaystyle{ \text{grant}(j) }[/math] message to the request on the top of its own request queue. Note that the requests at the top are the highest priority.
  • Place [math]\displaystyle{ P_k }[/math] into its request queue.
• Upon reception of a [math]\displaystyle{ \text{release}(i) }[/math] message, site [math]\displaystyle{ P_j }[/math] will:
  • Delete [math]\displaystyle{ P_i }[/math] from its request queue.
  • Send a [math]\displaystyle{ \text{grant}(j) }[/math] message to the request on the top of its request queue.

Critical section:

• Site [math]\displaystyle{ P_i }[/math] enters the critical section on receiving a [math]\displaystyle{ \text{grant} }[/math] message from all sites in [math]\displaystyle{ R_i }[/math].
• Upon exiting the critical section, [math]\displaystyle{ P_i }[/math] sends a [math]\displaystyle{ \text{release}(i) }[/math] message to all sites in [math]\displaystyle{ R_i }[/math].

Quorum set ([math]\displaystyle{ R_x }[/math]):
A quorum set must abide by the following properties:

1. [math]\displaystyle{ \forall i \,\forall j\, [R_i \bigcap R_j \ne \empty ] }[/math]
2. [math]\displaystyle{ \forall i\, [ P_i \in R_i ] }[/math]
3. [math]\displaystyle{ \forall i\, [ |R_i| = K ] }[/math]
4. Site [math]\displaystyle{ P_i }[/math] is contained in exactly [math]\displaystyle{ K }[/math] request sets

Therefore:

• [math]\displaystyle{ |R_i| \geq \sqrt{N-1} }[/math]

Performance

• Number of network messages; [math]\displaystyle{ 3 \sqrt{N} }[/math] to [math]\displaystyle{ 6 \sqrt{N} }[/math]
• 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.