Raymond's Algorithm is a token based algorithm for mutual exclusion

Mutual exclusion

Mutual exclusion algorithms are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections. A critical section is a piece of code in which a process or thread accesses a common resource...

 on a distributed system. It imposes a logical structure (a K-ary tree

K-ary tree

In graph theory, a k-ary tree is a rooted tree in which each node has no more than k children. It is also sometimes known as a k-way tree, an N-ary tree, or an M-ary tree.A binary tree is the special case where k=2....

) on distributed resources. As defined, each node has only a single parent, to which all requests to attain the token are made.

Nodal Properties

1. Each node has only one parent to whom received requests are forwarded
2. Each node maintains a FIFO
   FIFO
   FIFO is an acronym for First In, First Out, an abstraction related to ways of organizing and manipulation of data relative to time and prioritization...
   
    queue of requests
3. Each node forwards only a single request for each time that it sees the token;

Algorithm

1. If a node i wishes to receive the token in order to enter into its critical section
   Critical section
   In concurrent programming a critical section is a piece of code that accesses a shared resource that must not be concurrently accessed by more than one thread of execution. A critical section will usually terminate in fixed time, and a thread, task or process will have to wait a fixed time to...
   
   , 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
2. 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 after forwarding 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 if 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.

See also

• Ricart-Agrawala algorithm
  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...
  
  
• Lamport's Bakery Algorithm
  Lamport's bakery algorithm
  Lamport's bakery algorithm is a computer algorithm devised by computer scientist Leslie Lamport, which is intended to improve the safety in the usage of shared resources among multiple threads by means of mutual exclusion....
  
  
• 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.- Nodal properties :# Every process maintains a queue of pending requests for entering critical section order...
  
  
• Maekawa's Algorithm
  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 site needs only to seek permissions from a subset of other sites.- Terminology :...
  
  
• Suzuki-Kasami's Algorithm
• Naimi-Trehel's Algorithm