Lamport's distributed mutual exclusion algorithm

Lamport's Distributed Mutual Exclusion Algorithm is a contention-based algorithm for mutual exclusion on a distributed system.

Algorithm

Nodal properties

  1. Every process maintains a queue of pending requests for entering critical section in order. The queues are ordered by virtual time stamps derived from Lamport timestamps.[1]

Algorithm

Requesting process

  1. Pushing its request in its own queue (ordered by time stamps)
  2. Sending a request to every node.
  3. Waiting for replies from all other nodes.
  4. If own request is at the head of its queue and all replies have been received, enter critical section.
  5. Upon exiting the critical section, remove its request from the queue and send a release message to every process.

Other processes

  1. After receiving a request, pushing the request in its own request queue (ordered by time stamps) and reply with a time stamp.
  2. After receiving release message, remove the corresponding request from its own request queue.
  3. If own request is at the head of its queue and all replies have been received, enter critical section.

Message complexity

This algorithm creates 3(N  1) messages per request, or (N  1) messages and 2 broadcasts. 3(N  1) messages per request includes:

Drawbacks

There exist multiple points of failure.

See also

References

  1. Kshemkalyani, A., & Singhal, M. Chapter 9: Distributed Mutual Exclusion Algorithms. Distributed Computing: Principles, Algorithms, and Systems (Page 10 of 93). Cambridge University Press.
This article is issued from Wikipedia - version of the Wednesday, December 02, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.