A fair distributed mutual exclusion algorithm

This paper presents a fair decentralized mutual exclusion algorithm for dis tributed systems in which processes communicate by asynchronous message pas sing. The algorithm requires between N - 1 and 2(N - 1) messages per critic al section access. where N is the number of processes in the system. The ex act message complexity can be expressed as a deterministic function of conc urrency in the computation. The algorithm does not introduce any other over heads over Lamport's and Ricart-Agrawala's algorithms, which require 3(N - 1) and 2(N - 1) messages, respectively, per critical section access and are the only other decentralized algorithms that allow mutual exclusion access in the order of the timestamps of requests.