title: Maekawa's algorithm
text: # 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 $P_{i}$ sends a message ${\text{request}}(ts,i)$ to all sites in its quorum set $R_{i}$.
  
  Receiving site:
  
  * Upon reception of a ${\text{request}}(ts,i)$ message, the receiving site $P_{j}$ will:
     * If site $P_{j}$ does not have an outstanding ${\text{grant}}$ message (that is, a ${\text{grant}}$ message that has not been released), then site $P_{j}$ sends a ${\text{grant}}(j)$ message to site $P_{i}$.
     * If site $P_{j}$ has an outstanding ${\text{grant}}$ message with a process with higher priority than the request, then site $P_{j}$ sends a ${\text{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 ${\text{grant}}$ message with a process with lower priority than the request, then site $P_{j}$ sends an ${\text{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 ${\text{grant}}$ message.)
  * Upon reception of a ${\text{inquire}}(j)$ message, the site $P_{k}$ will:
     * Send a ${\text{yield}}(k)$ message to site $P_{j}$ if and only if site $P_{k}$ has received a ${\text{failed}}$ message from some other site or if $P_{k}$ has sent a yield to some other site but have not received a new ${\text{grant}}$.
  * Upon reception of a ${\text{yield}}(k)$ message, site $P_{j}$ will:
     * Send a ${\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 $P_{k}$ into its request queue.
  * Upon reception of a ${\text{release}}(i)$ message, site $P_{j}$ will:
     * Delete $P_{i}$ from its request queue.
     * Send a ${\text{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 ${\text{grant}}$ message from all sites in $R_{i}$.
  * Upon exiting the critical section, $P_{i}$ sends a ${\text{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}\bigcap R_{j}\neq \emptyset ]$
  * $\forall i\,[P_{i}\in R_{i}]$
  * $\forall i\,[|R_{i}|=K]$
  * 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.
  