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

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:

Receiving site:

Upon reception of a message, the receiving site will:
* If site does not have an outstanding message, then site sends a message to site.
* If site has an outstanding message with a process with higher priority than the request, then site sends a message to site and site queues the request from site.
* If site has an outstanding message with a process with lower priority than the request, then site sends an message to the process which has currently been granted access to the critical section by site.
Upon reception of a message, the site will:
* Send a message to site if and only if site has received a message from some other site or if has sent a yield to some other site but have not received a new.
Upon reception of a message, site will:
* Send a message to the request on the top of its own request queue. Note that the requests at the top are the highest priority.
* Place into its request queue.
Upon reception of a message, site will:
* Delete from its request queue.
* Send a message to the request on the top of its request queue.

Critical section:

Quorum set :

A quorum set must abide by the following properties: