Maekawa’s algorithm

Posted on November 30th, 2007 by admin

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 is running the Maekawa’s Algorithm
  • For any one request of the critical section:
    • The requesting site is the site which is requesting entry into the critical section.
    • The receiving site is every other site which is receiving the request from the requesting site.
  • ts refers to the local timestamp of the system according to its logical clock.


Algorithm

Requesting Site:

  • A requesting site <math>P_i</math> sends a message <math>request(ts, i)</math> to all sites in its quorum set <math>R_i</math>.

Receiving Site:

  • Upon reception of a <math>request(ts, i)</math> message, the receiving site <math>P_j</math> will:

    • If site <math>P_j</math> does not have an outstanding <math>grant</math> message (that is, a <math>grant</math> message that has not been released), then site <math>P_j</math> sends a <math>grant(j)</math> message to site <math>P_i</math>.
    • If site <math>P_j</math> has an outstanding <math>grant</math> message with a process with higher priority than the request, then site <math>P_j</math> sends a <math>failed(j)</math> message to site <math>P_i</math> and site <math>P_j</math> queues the request from site <math>P_i</math>.
    • If site <math>P_j</math> has an outstanding <math>grant</math> message with a process with lower priority than the request, then site <math>P_j</math> sends an <math>inquire(j)</math> message to the process which has currently been granted access to the critical section by site <math>P_j</math>. (That is, the site with the outstanding <math>grant</math> message.)
  • Upon reception of a <math>inquire(j)</math> message, the site <math>P_k</math> will:
    • Send a <math>yield(k)</math> message to site <math>P_j</math> if and only if site <math>P_k</math> has received a <math>failed</math> message from some other site or if <math>P_k</math> has sent a yield to some other site but have not received a new <math>grant</math>.
  • Upon reception of a <math>yield(k)</math> message, site <math>P_j</math> will:
    • Send a <math>grant(j)</math> message to the request on the top of its own request queue.
    • Place <math>P_k</math> into its request queue.
  • Upon reception of a <math>release(i)</math> message, site <math>P_j</math> will:
    • Delete <math>P_i</math> from its request queue.
    • Send a <math>grant(j)</math> message to the request on the top of its request queue.

Critical Section:

  • Site <math>P_i</math> enters the critical section on receiving a <math>grant</math> message from all sites in <math>R_i</math>.
  • Upon exiting the critical section, <math>P_i</math> sends a <math>release(i)</math> message to all sites in <math>R_i</math>.

Quorum Set (<math>R_x</math>):
A quorum set must abide by the following properties:

  1. <math>\forall i \forall j [R_i \bigcap R_j \ne \empty ]</math>
  2. <math>\forall i [ P_i \in R_i ]</math>
  3. <math>\forall i [ |R_i| = K ]</math>
  4. Site <math>P_i</math> is contained in exactly <math>K</math> request sets
Therefore:

  • <math>|R_i| \geq \sqrt{N-1}</math>


Performance

  • Number of network messages; <math>3 \sqrt{N}</math> to <math>6 \sqrt{N}</math>
  • Synchronization delay: 2 message propagation delays


See also

  • Lamport’s bakery algorithm
  • Lamport’s distributed mutual exclusion algorithm
  • Ricart-Agrawala algorithm
  • Suzuki-Kasami’s algorithm
  • Raymond’s algorithm


External links

  • “A sqrt(N) algorithm for mutual exclusion in decentralized systems” at The ACM Digital Library

Tags: , Uncategorized //

Discussion Area - Leave a Comment

You must be logged in to post a comment.

« Conservative two-phase locking WebMoney »