Maekawa algorithm

The Maekawa algorithm presented by Mamoru Maekawa in 1985 is used in a distributed system to regulate access to a critical section while guaranteeing mutual exclusion . The basic idea of ​​this algorithm is not to ask all processes (such as the Ricart-Agrawala algorithm ), but only a subset.

The algorithm guarantees the safety property (only a single process is in the critical section, but can lead to deadlocks without the use of vector time stamps (violates the lifeness property)).

Here one uses Voting sets . Every process has a voting set ( ) and consists of at least 2 voting sets. Each voting set contains K processes ( ), and two different voting sets have at least one element in common ( ). As an approximation for the optimum (the smallest possible K) is used. The processes are arranged in a matrix and the voting set is defined as all processes that are in the same column or row as . ${\displaystyle V_{i}}$ ${\displaystyle P_{i}}$ ${\displaystyle P_{i}\in V_{i}}$ ${\displaystyle \forall i\left|V_{i}\right|=K}$ ${\displaystyle \forall i\forall j[V_{i}\bigcap V_{j}\neq \emptyset ]}$ ${\displaystyle K=2{\sqrt {N}}-1}$ ${\displaystyle {\sqrt {N}}\times {\sqrt {N}}}$ ${\displaystyle V_{i}}$ ${\displaystyle P_{i}}$

algorithm

Every process has an internal status STATE with the values ​​RELEASED (start value), WANTED (the process wants to enter the critical section), HELD (the process is in the critical section) and a Boolean variable VOTED (another process has been given permission to to enter the critical section).

Does a process want to enter the critical section:

• set STATE = WANTED
• Request to all processes in the voting set
• wait for K to receive replies
• set STATE = HERO and enter the critical section

When leaving:

• set STATE = RELEASED
• Release to all processes in the voting set

When receiving a request:

• If STATE = HELD or VOTED = TRUE then
  • Place request in queue
• otherwise
  • Answer
  • set VOTED = TRUE

When receiving a share:

• Is the queue empty?
  • set VOTED = FALSE
• otherwise
  • Send reply to (and remove) the first process in the queue
  • set VOTED = TRUE

Message complexity

Three messages are exchanged with each process in : ${\displaystyle V_{i}}$

• a request
• a consent
• a release

All in all, messages are therefore required. ${\displaystyle 3\left|V_{i}\right|=3(2{\sqrt {N}}-1)}$

literature

• Mamoru Maekawa: A Algorithm for Mutual Exclusion in Decentralized Systems ${\displaystyle {\sqrt {n}}}$ . in: ACM Transactions on Computer Systems, 1985