This algorithm uses a spanning tree to reduce the number of messages exchanged per critical section execution.

The network is viewed as a graph, a spanning tree of a network is a tree that contains all the N nodes.

The algorithm assumes that the underlying network guarantees message delivery. All nodes of the network are ’completely reliable.

The algorithm operates on a minimal spanning tree of the network topology or a logical structure imposed on the network.

The algorithm assumes the network nodes to be arranged in an unrooted tree structure. Figure 4 shows a spanning tree of seven nodes A, B, C, D, E, F, and G. Messages between nodes traverse along the undirected edges of the tree.

A node needs to hold information about and communicate only to its immediate-neighboring nodes.

The concept of tokens used in token-based algorithms, this algorithm uses a concept of privilege.

Only one node can be in possession of the privilege (called the privileged node) at any time, except when the privilege is in transit from one node to another in the form of a PRIVILEGE message.

When there are no nodes requesting for the privilege, it remains in possession of the node that last used it.

The HOLDER Variables Each node maintains a HOLDER variable that provides information about the placement of the privilege in relation to the node itself. A node stores in its HOLDER variable the identity of a node that it thinks has the privilege or leads to the node having the privilege. For two nodes X and Y, if HOLDERX = Y, we could redraw the undirected edge between the nodes X and Y as a directed edge from X to Y. For instance, if node G holds the privilege, the Figure is redrawn as given below. The shaded node in Figure 5 represents the privileged node.

Now suppose node B that does not hold the privilege wants to execute the critical section. B sends a REQUEST message to HOLDERB, i.e., C, which in turn forwards the REQUEST message to HOLDERC, i.e., G. The privileged node G, if it no longer needs the privilege, sends the PRIVILEGE message to its neighbor C, which made a request for the privilege, and resets HOLDERG to C. Node C, in turn, forwards the PRIVILEGE to node B, since it had requested the privilege on behalf of B. Node C also resets HOLDERC to B.

The algorithm consists of the following routines:

ASSIGN PRIVILEGE

This is a routine sends a PRIVILEGE message. A privileged node sends a PRIVILEGE message if it holds the privilege but is not using it, its REQUEST Q is not empty, and The element at the head of its REQUEST Q is not “self.”

MAKE REQUEST

This is a routine sends a REQUEST message. An unprivileged node sends a REQUEST message if it does not hold the privilege, its REQUEST Q is not empty, i.e., it requires the privilege for itself, or on behalf of one of its immediate neighboring nodes, and it has not sent a REQUEST message already.