{{See also|Lamport's bakery 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.<ref>Kshemkalyani, A., & Singhal, M. Chapter 9: Distributed Mutual Exclusion Algorithms. Distributed Computing: Principles, Algorithms, and Systems (Page 10 of 93). Cambridge University Press. </ref>
===Algorithm===
'''Requesting process'''
# Pushing its request in its own queue (ordered by time stamps) # 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 (ordered by time stamps) 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(''N'' − 1) messages per request, or (''N'' − 1) messages and 2 broadcasts. 3(''N'' − 1) messages per request includes: * (''N'' − 1) total number of requests * (''N'' − 1) total number of replies * (''N'' − 1) 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(''N'' − 1) messages per entry/exit into the critical section.
==See also== * Ricart–Agrawala algorithm (an improvement over Lamport's algorithm) * Lamport's bakery algorithm * Raymond's algorithm * Maekawa's algorithm * Suzuki–Kasami algorithm * Naimi–Trehel algorithm
==References== {{Reflist}}
{{Comp-sci-stub}}
Category:Concurrency control algorithms Category:Distributed computing