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]
Algorithmedit
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 complexityedit
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
Drawbacksedit
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.
^Kshemkalyani, A., & Singhal, M. Chapter 9: Distributed Mutual Exclusion Algorithms. Distributed Computing: Principles, Algorithms, and Systems (Page 10 of 93). Cambridge University Press.
This computer science article is a stub. You can help Wikipedia by expanding it.
lamport, distributed, mutual, exclusion, algorithm, also, lamport, bakery, algorithm, lamport, distributed, mutual, exclusion, algorithm, contention, based, algorithm, mutual, exclusion, distributed, system, contents, algorithm, nodal, properties, algorithm, m. See also Lamport s bakery algorithm Lamport s Distributed Mutual Exclusion Algorithm is a contention based algorithm for mutual exclusion on a distributed system Contents 1 Algorithm 1 1 Nodal properties 1 2 Algorithm 2 Message complexity 3 Drawbacks 4 See also 5 ReferencesAlgorithm editNodal properties edit 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 edit 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 editThis 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 releasesDrawbacks editThis 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 editRicart Agrawala algorithm an improvement over Lamport s algorithm Lamport s bakery algorithm Raymond s algorithm Maekawa s algorithm Suzuki Kasami algorithm Naimi Trehel algorithmReferences edit Kshemkalyani A amp Singhal M Chapter 9 Distributed Mutual Exclusion Algorithms Distributed Computing Principles Algorithms and Systems Page 10 of 93 Cambridge University Press nbsp This computer science article is a stub You can help Wikipedia by expanding it vte Retrieved from https en wikipedia org w index php title Lamport 27s distributed mutual exclusion algorithm amp oldid 1157102062, wikipedia, wiki, book, books, library,
