Lamport's Distributed Mutual Exclusion Algorithm

From Wikipedia, the free encyclopedia

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

Contents

[edit] Algorithm

[edit] Nodal Properties

  1. Every process maintains a queue of pending requests for entering critical section ordered according to the logical time-stamp.

[edit] Algorithm

Requesting Process

  1. Enters its request in its own queue.
  2. Sends a request to every node.
  3. Wait for replies from all other nodes.
  4. If own request is at the head of the queue and all replies have been received, enter critical section.
  5. Upon exiting the critical section, send a release message to every process.

Other Processes

  1. After receiving a request, send a reply and enter the request in the request queue
  2. After receiving release message, remove the corresponding request from the request queue.
  3. If own request is at the head of the queue and all replies have been received, enter critical section.

[edit] Message Complexity

This algorithm creates 3(N-1) messages per request.

[edit] Drawbacks

  1. There exist multiple points of failure.

[edit] See also