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 ordered according to the logical time-stamp.

Algorithm

Requesting Process

1. Sends a request to every process.
2. After all replies are collected, enter its own request in its own queue
3. If own request is at the head of the queue, enter critical section.
4. 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 queue
2. After receiving release message, remove the corresponding request from the queue.
3. If own request is at the head of the queue, enter critical section.

Message Complexity

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

Drawbacks

1. There exist multiple points of failure.

See also

• Ricart-Agrawala algorithm
• Lamport's Bakery Algorithm
• Raymond's Algorithm
• Maekawa's Algorithm
• Suzuki-Kasami's Algorithm