Raymond’s algorithm is a token-based algorithm for mutual exclusion on adistributed system.
The Raymond’s algorithm is invented in 1989.It imposes alogical structure(a k-ary tree) on distributed resources. As defined, each nodehas 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 nodehas variable “Holder” that points to its parent on the path to the root. Root’sholder variable points to itself. Each node maintains a FIFO queue of requestseach time that it sees the token4.
At first, node add self in its request queue and send to itsparent. The parent add request in its request queue. If parent does not havetoken it will request to its parent until it reach root node. When the rootreceives a REQUEST, then the root sendthe 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 queueand send token to that node.
If queue is non non-empty, send a REQUEST messageto the parent1. This algorithm uses a spanning tree to reduce the number ofmessages exchanged per critical section execution. It assumes that theunderlying network guarantees message delivery. All nodes of the network arecompletely reliable4. Raymond’s algorithm is guaranteed to be 0(log n) percritical 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 suggestionfor the recovery.
Uses a static logical tree structure. Average messages:0(logN) as average distance between 2nodes in the tree is 0(log N).Synchronizationdelay:(T log N)/2,as average distance between 2sites to successively execute CSis (log N)/2.Greedy approach: Intermediate site getting the token may enter CS instead offorwarding it down. Affects fairness, may cause starvation1.
The advantage ofRaymond’s algorithm is that each process explicitly requests for a token andthe token is moved only when no process if the process knows of a pendingrequest4. A node needs to hold information about and contact only to itscurrently neighboring nodes. Raymond’s algorithm works on a concept ofprivilege. The design of distributed MUTEX scheme is difficult because thisalgorithm have to deal with irregular message delays and partial knowledge ofthe system state. The algorithm does not require sequence numbers as itoperates correctly despite message overtaking.