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.[1]
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.
gollark: Also, you don't have to deal with issues caused by gloves or masks or whatever. As much.
gollark: I'm not really sure why people are so obsessed with face/fingerprint unlock. I mean, you can type in a PIN very fast, and it's generally more secure to rely on knowledge rather than some biometrics which you can't change.
gollark: Hmm, can retinas actually send pain signals or anything?
gollark: I have fun videos like "20170928-NFsVGsaCvsk Sustainability! This Couple Cooks All The Meat That Comes Flying Out Of The Portal In Its Backyard.mp4", "20200724-OTKZ0Kv8WfE Electrical Exothermic Welding... A Thermite walks into a bar....mp4", "20200416-vtN4tkvcBMA How I made a basketball hoop that always goes in.mp4", and "20181102-BXU5ONIG4kw The Benefit of Fragmenting your Hard Drive.mp4".
gollark: Great, saved that, now I can steal military vehicles!
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's algorithm
References
- Kshemkalyani, A., & Singhal, M. Chapter 9: Distributed Mutual Exclusion Algorithms. Distributed Computing: Principles, Algorithms, and Systems (Page 10 of 93). Cambridge University Press.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.