Quorum Generation Algorithm Based On The Number Of Repetitions Research

In distributed system, the critical resources are viewed of mutual exclusion, so the first problem is sloving the distributed mutual exclusion algorithms in the distributed system. The distributed mutual algorithms is mainly divided the distributed mutual exclusion algorithms based on competition and the distributed mutual exclusion algorithm based on the token. The distributed mutual exclusion algorithms based on competition have big message complexity, synchronization time is short, and symmetry is good. The distributed mutual exclusion algorithm based on competion is divided into totally mutual exclusion algorithm and locally mutual exclusion algortthm. The totally mutual exclusion algorithm has good symmetry, but the message complexity is greatly and the size of the system is limited. The locally mutual exclusion algortthm reduces the message complexity and can adapt to the larger system, but it increase overhead of the quorum generation algorithm in time and space. The operation process of locally mutual exclusion algortthm has two steps:the first step is quorum generation algorithm,the second step is mutual exclusion algorithms. We study the quorum generation algorithm in this paper.In distributed mutual exclusion algorithm based on competition, the algorithm has the shortest quorum length. Guranteeing the quorum length is the shortest, the time complexity and space complexity is the lowest, this is the target for the researchers of quorum generation algorithm of distributed mutual exclusion. The distributed mutual exclusion algorithm based on competition is studyed in this paper, and we found that the current research on specific topological structure of the distributed mutual exclusion algorithm is more fully. This kind of algorithm is simple, not only the algorithm is suit the specific system nodes, but also the quorum generation algorithm is not symmetrical. Therefore, the quorum generation algorithm is important for any system nodes. When the quorum generation algorithm is suitable for arbitrary system at the same time, and ensures the quorum structure is simple and symmetrical, this is more important for the current researchers. The cyclic quorum is satisfied to the two conditions. The quorum generation algorithm based on the number of repetitions research is one of the cyclic quorum algorithms.In the universal distributed mutual exclusion algorithms, most of algorithm can quickly generate quorum, but the quorum length is bigger. Therefore, the target of universal distributed mutual exclusion algorithms is the shortest quorum length, and the time complexity and space complexity is also the lowest. However, when the quorum length is the shortest (the quorum lenght is N), the kind of algorithms is few. These algorithms is similar the the exhaustive method.A new quorum generation algorithm for symmetric and cyclic quorum has been presented in this pater. The algorithm aim guarantee that the quorum length is the shortest and the algorithm reduce the time complexity and space complexity. The algorithm is based on the theory of relaxed cyclic difference set, and judged by the conditions of maximum allowable number of repetitions, adding elements to the quorum. Based on the research of the algorithm further, the paper puts forward a concept of the quorum limit and the optimization method. When the system nodes does not exist the shortest cyclic quorum, the optimization method reduce redundant calculation counts.Compared with the exhaustive method, the algorithm based on the number of repetitions and the optimization method solve the shortest cyclic quorum in this paper, the time complexity is decreased obviously. The algorithm provides reference and help for the search of the shortest cyclic quorum generation algorithm.