An efficient method for mutual exclusion in truly distributed systems

Many operations in a distributed system require mutual exclusion to guarantee correctness. Quorum methods have been widely proposed for implementing mutual exclusion. Majority voting is the best known quorum method. It has the merit of simplicity, but may incur high message overhead. The tree algorithm is an efficient structured quorum method for mutual exclusion problems. The quorums generated by a tree algorithm are smaller on average than those generated by a majority voting. However, the tree algorithm enforces a highly biased treatment to the nodes at different levels. This affects its performance in a distributed system where the nodes have similar characteristics. We propose a new structured quorum method which treats the nodes more evenly than the tree algorithm yet still preserves a satisfactory availability. We believe that this method is desirable for implementing mutual exclusion in a truly distributed system