Raymond's algorithm

Raymond's algorithm is a lock based algorithm that gives the nodes of a distributed system mutual exclusion, meaning only one node at a time may enter its critical section. It arranges the nodes in a logical tree, a K-ary tree, in which each node has a single parent and sends every request for the token to that parent. A node that wants the token puts the requester in a first-in first-out queue and, if the queue was empty, asks its own parent in turn. When the node holding the token receives a request it passes the token down the path toward the requester and makes the receiving node its new parent, so the root of the tree always follows the token. A node uses the token to enter its critical section only when it reaches the head of its own queue. Because requests travel along tree paths, the algorithm needs O(log n) messages per critical section entry when the processors form a K-ary tree, and each processor stores at most O(log n) bits because it tracks only a constant number of neighbors.