📑 Table of Contents▼
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

edit

Nodal properties

edit
  1. 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

  1. Pushing its request in its own queue (ordered by time stamps)
  2. Sending a request to every node.
  3. Waiting for replies from all other nodes.
  4. If own request is at the head of its queue and all replies have been received, enter critical section.
  5. Upon exiting the critical section, remove its request from the queue and send a release message to every process.

Other processes

  1. After receiving a request, pushing the request in its own request queue (ordered by time stamps) and reply with a time stamp.
  2. After receiving release message, remove the corresponding request from its own request queue.

Message complexity

edit

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

edit

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

edit

References

edit
  1. ^ Kshemkalyani, A., & Singhal, M. Chapter 9: Distributed Mutual Exclusion Algorithms. Distributed Computing: Principles, Algorithms, and Systems (Page 10 of 93). Cambridge University Press.
Stub icon

This computer science article is a stub. You can help Wikipedia by adding missing information.

📚 Artikel Terkait di Wikipedia

Mutual exclusion

write are permitted, since it leads to data inconsistency). Mutual exclusion algorithms ensure that if a process is already performing write operation

List of algorithms

algorithm Mutual exclusion Lamport's Distributed Mutual Exclusion Algorithm Naimi-Trehel's log(n) Algorithm Maekawa's Algorithm Raymond's Algorithm Ricart–Agrawala

Leslie Lamport

algorithms to solve many fundamental problems in distributed systems, including: the Paxos algorithm for consensus, the bakery algorithm for mutual exclusion

Ashok Agrawala

This algorithm is an extension and optimization of Lamport's Distributed Mutual Exclusion Algorithm. Agrawala received B.E. and M.E. degrees in Electrical

Raymond's algorithm

Raymond's Algorithm is a lock based algorithm for mutual exclusion on a distributed system. It imposes a logical structure (a K-ary tree) on distributed resources

Ricart–Agrawala algorithm

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

Maekawa's algorithm

Maekawa'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

Naimi–Trehel algorithm

Naimi–Trehel algorithm is an algorithm for achieving mutual exclusion in a distributed system. Unlike Lamport's distributed mutual exclusion algorithm and its