Lamport's Distributed Mutual Exclusion Algorithm
- 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 ordered according to the logical time-stamp.
Algorithm
Requesting Process
# Enters its request in its own queue.
# 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
# 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.
Drawbacks
# There exist multiple points of failure.
See also
* Ricart-Agrawala algorithm
* Lamport's Bakery Algorithm
* Raymond's Algorithm
* Maekawa's Algorithm
* Suzuki-Kasami's Algorithm
*Naimi-Trehel's Algorithm
Wikimedia Foundation.
2010.
Look at other dictionaries:
Mutual exclusion — For the concept, see Mutually exclusive events. mutex redirects here. For the computer program object that negotiates mutual exclusion among threads, see lock (computer science). Mutual exclusion (often abbreviated to mutex) algorithms are used… … Wikipedia
Lamport — may refer to:;Places *Lamport, Buckinghamshire, England. *Lamport, Northamptonshire, England. **Lamport Hall is nearby **Northampton Lamport Railway also nearby;People *Allan A. Lamport, Mayor of Toronto, 1952 ndash;1954 *Leslie Lamport, American … Wikipedia
Ricart-Agrawala algorithm — The 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. It was… … Wikipedia
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 site needs only to seek permissions from a subset of other sites. Contents 1 Algorithm 1.1 Terminology 1.2 Algorithm … Wikipedia
Raymond's algorithm — is a token based algorithm for mutual exclusion on a distributed system. It imposes a logical structure (a K ary tree) on distributed resources. As defined, each node has only a single parent, to which all requests to attain the token are made.… … Wikipedia
Leslie Lamport — Infobox Scientist name = Leslie Lamport image width = 150px caption = birth date = February 7, 1941 birth place = New York City, New York death date = death place = residence = citizenship = nationality = ethnicity = field = Computer Science work … Wikipedia
Algorithme de Naimi-Trehel — L algorithme de Naimi Trehel assure l exclusion mutuelle dans les systèmes distribués. Cet algorithme réduit le nombre moyen de messages à log(n)en introduisant une structure arborescente logique et un jeton. L algorithme a été présenté en 1987… … Wikipédia en Français
Dijkstra Prize — The Edsger W. Dijkstra Prize in Distributed Computing is given for outstanding papers on the principles of distributed computing, whose significance and impact on the theory and/or practice of distributed computing has been evident for at least a … Wikipedia
Parallel computing — Programming paradigms Agent oriented Automata based Component based Flow based Pipelined Concatenative Concurrent computing … Wikipedia
Autostabilisation — L autostabilisation, ou auto stabilisation, est la propriété d un système réparti, composé de plusieurs machines capables de communiquer entre elles, qui consiste, lorsque le système est mal initialisé ou perturbé, à retourner automatiquement à… … Wikipédia en Français
