Raymond’s algorithm is invented in 1989.It imposes a

Raymond’s algorithm is a token-based algorithm for mutual exclusion on a
distributed system. The Raymond’s algorithm is invented in 1989.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 made3.
It forms a directed tree(logical)with the token token-holder as root. Each node
has variable “Holder” that points to its parent on the path to the root. Root’s
holder variable points to itself. Each node maintains a FIFO queue of requests
each time that it sees the token4. At first, node  add self in its request queue and send to its
parent. The parent add request in its request queue. If parent does not have
token it will request to its parent until it reach root node. When the root
receives a REQUEST, then  the root send
the token to the requesting node and set holder variable to point to that node.
When a node receives the token, then the node delete first entry from the queue
and send token to that node. If queue is non non-empty, send a REQUEST message
to the parent1. This algorithm uses a spanning tree to reduce the number of
messages exchanged per critical section execution. It assumes that the
underlying network guarantees message delivery. All nodes of the network are
completely reliable4. Raymond’s algorithm is guaranteed to be 0(log n) per
critical section entry if the processors are organized into a k-ary tree. Additionally,
each processor needs to store at must 0(log n)bits because it must track 0(1)
neighbors. This algorithm discusses the effect of failures and gives suggestion
for the recovery. Uses a static logical tree structure. Average messages:0(log
N) as average distance between 2nodes in the tree is 0(log N).Synchronization
delay:(T log N)/2,as average distance between 2sites to successively execute CS
is (log N)/2.Greedy approach: Intermediate  site getting the token may enter CS instead of
forwarding it down. Affects fairness, may cause starvation1. The advantage of
Raymond’s algorithm is that each process explicitly requests for a token and
the token is moved only when no process if the process knows of a pending
request4. A node needs to hold information about and contact only to its
currently neighboring nodes. Raymond’s algorithm works on a concept of
privilege. The design of distributed MUTEX scheme is difficult because this
algorithm have to deal with irregular message delays and partial knowledge of
the system state. The algorithm does not require sequence numbers as it
operates correctly despite message overtaking.