Maekawa's algorithm explained

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

Receiving site:

• Upon reception of a

request (ts, i) message, the receiving site P _{j} will:

• • If site

P _{j} does not have an outstanding grant message (that is, a grant message that has not been released), then site P _{j} sends a grant (j) message to site P _{i} .

• • If site

P _{j} has an outstanding grant message with a process with higher priority than the request, then site P _{j} sends a 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 grant message with a process with lower priority than the request, then site P _{j} sends an 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 grant message.)

• Upon reception of a

inquire (j) message, the site P _{k} will:

• • Send a

yield (k) message to site P _{j} if and only if site P _{k} has received a failed message from some other site or if P _{k} has sent a yield to some other site but have not received a new grant .

• Upon reception of a

yield (k) message, site P _{j} will:

• • Send a

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

release (i) message, site P _{j} will:

• • Delete

P _{i} from its request queue.

• • Send a

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 grant message from all sites in R _{i} .

• Upon exiting the critical section,

P _{i} sends a 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} c ap R _{j} \ne \empty ] \forall i [ P _{i} \in R _{i} ] \forall i [ |R _{i|} = K ]

1. 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
• The algorithm can deadlock without protections in place.^{[1] [2]}

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.

Notes and References

1. Web site: Maekawa's Mutual Exclusion Algorithm: Voting approach.
2. Web site: Distributed Mutual Exclusion.