We present an algorithm for distributed mutual exclusion in a computer network of N nodes
that communicate by messages rather than shared memory. The algorithm uses a spanning
tree of the computer network, and the number of messages exchanged per critical section
depends on the topology of this tree. However, typically the number of messages exchanged
is O (log N) under light demand, and reduces to approximately four messages under
saturated demand.
Each node holds information only about its immediate neighbors in the spanning tree
rather than information about all nodes, and failed nodes can recover necessary
information from their neighbors. The algorithm does not require sequence numbers as it
operates correctly despite message overtaking.