Research Of Quorum Generation Algorithms For Distributed Mutual Exclusion

The high running efficiency is an important standard for measuring an algorithm. The length, symmetry and generation complexity of the distributed mutual exclusion quorum will directly affect the time complexity, symmetry and system scale of these distributed mutual exclusion algorithms based on it. Therefore, this thesis mainly concentrates on analysing and researching the distributed mutual exclusion quorum generation algorithms.Based on the formerly distrubuted mutual exclusion algorithms, and according as the quorum's condition which is proposed in Maekawa algorithm, an initialization method has been proposed, and the new method uses the triangular grid structure. With using this method, two algorithms which based on cyclic coding and relaxed cyclic difference set have been improved.Through increasing the number of the quorum's initialization node, the algorithm which based on cyclic coding has been improved. The length of the quorums is between 2N and 2 N , in that case, this method increases the algorithm's running rate. Then, the improved algorithm is optimized by adding a motion parameter. It makes the nodes of the quorums tending to uniformity, so the flexibility and usability of the quorums have been enhanced.Based on relaxed cyclic difference set and triangular grid structure, a new generation algorithm has been proposed in this paper. Through increasing the number of initialization nodes, this algorithm makes the time complexity greatly reduced, at the same time the length of the quorums which it generated is between 2N and 2 N .