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
- 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.
Algorithm
Requesting process
- Pushing its request in its own queue
- Sending a request to every node.
- Waiting for replies from all other nodes.
- If own request is at the head of its queue and all replies have been received, enter critical section.
- Upon exiting the critical section, remove its request from the queue and send a release message to every process.
Other processes
- After receiving a request, pushing the request in its own request queue and reply with a time stamp.
- After receiving release message, remove the corresponding request from its own request queue.
Message complexity
This algorithm creates 3 messages per request, or messages and 2 broadcasts. 3 messages per request includes:
- total number of requests
- total number of replies
- total number of releases
Drawbacks
This algorithm has several disadvantages. They are:
- It is very unreliable as failure of any one of the processes will halt progress.
- It has a high message complexity of 3 messages per entry/exit into the critical section.
