Raymond's algorithm

Raymond's algorithm

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.

Algorithm

Nodal Properties

# Each node has only one parent to whom received requests are forwarded
# Each node maintains a FIFO queue of requests
# Makes only forwards only a single request for each time that it sees the token;

Algorithm

# If a node "i" wishes the receive the token in order to enter into its critical section, it sends a request to its parent, node "j".
#* If node "j" FIFO is empty, node "j" shifts "i" into the its FIFO queue; "j" then issues a request to its parent, "k", that it desires the token
#* If node "j" FIFO queue is "not" empty, it simply shifts "i" into the queue
# When node "j" receives the token from "k", it forwards the token to "i" and "i" is removed from the queue of "j"
#* If the queue of "j" is not empty afterwarding the token to "i", "j" must issue a request to "i" in order to get the token back

"Note": If "j" wishes to request a token, and its queue is "not" empty, then it places itself into its own queue. Node "j" will utilize the token to enter into its critical section iff it is at the head of the queue when the token is received.

Complexity

Raymond's algorithm is guaranteed to be "O(log n)" per critical section entry if the processors are organized into a "K-ary" tree. Additionally, each processor needs to store at most "O(log n)" bits because it must track "O(1)" neighbors. [R. Chow, T. Johnson; "Distributed Operating Systems & Algorithms; Addison-Wesley, 1997.]

References

See also

* Ricart-Agrawala algorithm
* Lamport's Bakery Algorithm
* Lamport's Distributed Mutual Exclusion Algorithm
* Maekawa's Algorithm
* Suzuki-Kasami's Algorithm
*Naimi-Trehel's Algorithm


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • 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

  • 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… …   Wikipedia

  • Kahan summation algorithm — In numerical analysis, the Kahan summation algorithm (also known as compensated summation) significantly reduces the numerical error in the total obtained by adding a sequence of finite precision floating point numbers, compared to the obvious… …   Wikipedia

  • OPTICS algorithm — OPTICS ( Ordering Points To Identify the Clustering Structure ) is an algorithm for finding density based clusters in spatial data. It was presented by Mihael Ankerst, Markus M. Breunig, Hans Peter Kriegel and Jörg Sander[1]. Its basic idea is… …   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

  • Edward D. Thalmann — Infobox Military Person name= Edward Deforest Thalmann born= birth date|1945|04|03 Death date and age|2004|07|24|1945|04|03 died= placeofbirth= Jersey City, New Jersey placeofdeath= Durham, North Carolina caption= nickname=|allegiance=… …   Wikipedia

  • Donald Knuth — Donald Ervin Knuth Donald Knuth at a reception for the Open Content Alliance, October 25, 2005 Born …   Wikipedia

  • List of important publications in computer science — This is a list of important publications in computer science, organized by field. Some reasons why a particular publication might be regarded as important: Topic creator – A publication that created a new topic Breakthrough – A publication that… …   Wikipedia

  • Computational complexity theory — is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other. In this context, a… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”