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:

• .

Receiving site:

will:

• .

• .

• message.)

will:

• if and only if.

will:

• message to the request on the top of its own request queue. Note that the requests at the top are the highest priority.

• into its request queue.

will:

• from its request queue.

• message to the request on the top of its request queue.

Critical section:

• .

• .

): A quorum set must abide by the following properties:

1. request sets

Performance

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