Samiksha Jaiswal (Editor)

Maekawa's algorithm

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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.

Contents

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 request ( t s , i ) to all sites in its quorum set R i .

    • Receiving site:

  • Upon reception of a request ( t s , i ) message, the receiving site P j will:
  • If site P j does not have an outstanding grant message (that is, a grant message that has not been released), then site P j sends a grant ( j ) message to site P i .
  • If site P j has an outstanding grant message with a process with higher priority than the request, then site P j sends a 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 grant message with a process with lower priority than the request, then site P j sends an 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 grant message.)
  • Upon reception of a inquire ( j ) message, the site P k will:
  • Send a yield ( k ) message to site P j if and only if site P k has received a failed message from some other site or if P k has sent a yield to some other site but have not received a new grant .
  • Upon reception of a yield ( k ) message, site P j will:
  • Send a 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 release ( i ) message, site P j will:
  • Delete P i from its request queue.
  • Send a 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 grant message from all sites in R i .
  • Upon exiting the critical section, P i sends a release ( i ) message to all sites in R i .

    • Quorum set ( R x ):
    A quorum set must abide by the following properties:

    1. ∀ i ∀ j [ R i ⋂ R j ≠ ∅ ]
    2. ∀ i [ P i ∈ R i ]
    3. ∀ i [ | R i | = K ]
    4. Site P i is contained in exactly K request sets
    Therefore:
  • | R i | ≥ N − 1

    • Performance

  • Number of network messages; 3 N to 6 N
  • Synchronization delay: 2 message propagation delays

    • References

    Maekawa's algorithm Wikipedia
    (Text) CC BY-SA