View source for Raymond's algorithm

'''Raymond's Algorithm''' is a lock based algorithm for [[Mutual exclusion|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 (computing and electronics)|FIFO]] queue of requests each time that it sees the token;
# If any node is forwarding privilege to other node and has non-empty queue then it forwards a request message along

===Algorithm===

# If a node ''i'' (not holding the token) wishes to receive the token in order to enter into its [[Critical section|critical section]], it sends a request to its parent, node ''j''.
#* If node ''j'' FIFO is empty, node ''j'' shifts ''i'' into 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 ''k'' has token and receives the request from ''j'' it sends token to ''j'' and sets ''j'' as its parent
# 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.<ref>R. Chow, T. Johnson; ''Distributed Operating Systems & Algorithms''; Addison-Wesley, 1997.</ref>

== References ==
<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

[[Category:Concurrency control algorithms]]

{{Sourceattribution|Raymond's algorithm}}