Lamport's Distributed Mutual Exclusion Algorithm
Encyclopedia
Lamport's Distributed Mutual Exclusion Algorithm is a contention-based algorithm for mutual exclusion
on a distributed system.
Other processes
Mutual exclusion
Mutual exclusion algorithms are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections. A critical section is a piece of code in which a process or thread accesses a common resource...
on a distributed system.
Nodal properties
- Every process maintains a queue of pending requests for entering critical section order. The queues are ordered by virtual time stamps derived from Lamport timestampsLamport timestampsThe algorithm of Lamport timestamps is a simple algorithm used to determine the order of events in a distributed computer system. As different nodes or processes will typically not be perfectly synchronized, this algorithm is used to provide a partial ordering of events with minimal overhead, and...
.
Algorithm
Requesting process- Enters its request in its own queue (ordered by time stamps)
- Sends a request to every node.
- Wait for replies from all other nodes.
- If own request is at the head of the queue and all replies have been received, enter critical section.
- Upon exiting the critical section, send a release message to every process.
Other processes
- After receiving a request, send a reply and enter the request in the request queue (ordered by time stamps)
- After receiving release message, remove the corresponding request from the request queue.
- If own request is at the head of the 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.See also
- Ricart-Agrawala algorithmRicart-Agrawala algorithmThe Ricart-Agrawala Algorithm is an algorithm for mutual exclusion on a distributed system. This algorithm is an extension and optimization of Lamport's Distributed Mutual Exclusion Algorithm, by removing the need for release messages...
- Lamport's Bakery AlgorithmLamport's bakery algorithmLamport's bakery algorithm is a computer algorithm devised by computer scientist Leslie Lamport, which is intended to improve the safety in the usage of shared resources among multiple threads by means of mutual exclusion....
- Raymond's AlgorithmRaymond's algorithmRaymond's Algorithm is a token based algorithm for mutual exclusion on a distributed system. It imposes a logical structure on distributed resources...
- Maekawa's AlgorithmMaekawa's algorithmMaekawa's algorithm is an algorithm for mutual exclusion on a distributed system. The basis of this algorithm is a quorum like approach where any one site needs only to seek permissions from a subset of other sites.- Terminology :...
- Suzuki-Kasami's AlgorithmSuzuki-Kasami algorithmThe Suzuki-Kasami algorithm is a token-based algorithm for achieving mutual exclusion in distributed systems.-Main points:Some Points about the Suzuki Kasami algorithm are:* Only the site currently holding the token can access the CS...
- Naimi-Trehel's Algorithm