An efficient mutual exclusion method in distributed systems

• Main Author: Chen, Hao
• Other Authors: Memorial University of Newfoundland. Dept. of Computer Science
• Format: Thesis
• Language: English
• Published: 1994
• Subjects: Distributed operating systems (Computers); Electronic data processing > Distributed processing; Computer algorithms; Newfoundland studies; University of Newfoundland
• Online Access: http://collections.mun.ca/cdm/ref/collection/theses2/id/181686

Thesis (M.Sc.)--Memorial University of Newfoundland, 1994. Computer Science Bibliography: leaves 65-70. Many operations in a distributed system require mutual exclusion to guarantee correctness. Quorum methods have been widely proposed for implementing mutual exclusion. Majority quorum consensus is the best known quorum method. It has the merit of simplicity, but may incur high message overhead. Tree algorithm is an efficient structured quorum method to the mutual exclusion problems. The quorums generated by a tree algorithm are smaller on the average than those by a majority quorum consensus. 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 called triangular net quorum algorithm, which treats the nodes more evenly than the tree algorithm while preserving a satisfactory availability, as well as lowering average quorum size. We believe that this method is desirable for implementing mutual exclusion in a truly distributed system.