Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Lamport's distributed mutual exclusion algorithm
open-in-new
<h2 id="algorithm">Algorithm</h2> <h3>Nodal properties</h3> <ol><li>Every process maintains a queue of pending requests for entering critical section in order. The queues are ordered by virtual time stamps derived from <a href="/facts/Lamport_timestamps/Dpxw6Ia4">Lamport timestamps</a>.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a></li></ol> <h3>Algorithm</h3> <p>Requesting process </p> <ol><li>Pushing its request in its own queue (ordered by time stamps)</li> <li>Sending a request to every node.</li> <li>Waiting for replies from all other nodes.</li> <li>If own request is at the head of its queue and all replies have been received, enter critical section.</li> <li>Upon exiting the critical section, remove its request from the queue and send a release message to every process.</li></ol> <p>Other processes </p> <ol><li>After receiving a request, pushing the request in its own request queue (ordered by time stamps) and reply with a time stamp.</li> <li>After receiving release message, remove the corresponding request from its own request queue.</li></ol> <h2 id="message-complexity">Message complexity</h2> <p>This algorithm creates 3(<i>N</i> − 1) messages per request, or (<i>N</i> − 1) messages and 2 broadcasts. 3(<i>N</i> − 1) messages per request includes: </p> <ul><li>(<i>N</i> − 1) total number of requests</li> <li>(<i>N</i> − 1) total number of replies</li> <li>(<i>N</i> − 1) total number of releases</li></ul> <h2 id="drawbacks">Drawbacks</h2> <p>This algorithm has several disadvantages. They are: </p> <ul><li>It is very unreliable as failure of any one of the processes will halt progress.</li> <li>It has a high message complexity of 3(<i>N</i> − 1) messages per entry/exit into the critical section.</li></ul> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Ricart%E2%80%93Agrawala_algorithm/hrK9KoVS">Ricart–Agrawala algorithm</a> (an improvement over Lamport's algorithm)</li> <li><a href="/facts/Lamport%27s_bakery_algorithm/LhNIQ02p">Lamport's bakery algorithm</a></li> <li><a href="/facts/Raymond%27s_algorithm/zWQ0WpgN">Raymond's algorithm</a></li> <li><a href="/facts/Maekawa%27s_algorithm/oMsm7jML">Maekawa's algorithm</a></li> <li><a href="/facts/Suzuki%E2%80%93Kasami_algorithm/S33XLoHD">Suzuki–Kasami algorithm</a></li> <li>Naimi–Trehel algorithm</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Kshemkalyani, A., & Singhal, M. Chapter 9: Distributed Mutual Exclusion Algorithms. Distributed Computing: Principles, Algorithms, and Systems (Page 10 of 93). Cambridge University Press. <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> </ol>