A Quorum Generation Algorithm For Distributed Mutual Exclusion Basing On The Banker’s Algorithm

Distributed Mutual Exclusion efficiency of the system depends to a great extent to get the efficiency of the requesting node. Quorum generation algorithms to achieve the optimal length, but the time complexity is too high; If you want to get a quick generation, but also a corresponding increase in the length of the quorum of. Therefore, to design one and the optimal length and the optimum time complexity is one of the quorum generation algorithm become the urgent need to address the problem.This paper" analyzes the distributed mutual exclusion algorithm background and development status. On this basis, focusing on the characteristics of distributed mutual exclusion system, and then analyzes the quorum sequence of the significance of the system. Also described in detail the advantages and disadvantages of the original quorum generation algorithms. Situation for the time complexity and space complexity can not have at the same time, a new type of quorum generation concept.This article focuses on content and innovations in the following aspects.1.Create a distributed mutual exclusion quorum generation algorithm of the mathematical model. By contrast the characteristics of the existing quorum algorithm determine a good quorum of the standards has. Clear direction.2.Analysis of the similarities of the banker’s algorithm and the quorum generation algorithms. According to the banker’s algorithm for deadlock avoidance, and security process sequence of recursive thinking. This idea draws on the quorum generation algorithms. By the addition of the quorum the remaining length of this variable, the quorum of the remaining length of the array of node status as a boundary condition can be determined to apply to enter the legitimacy of the quorum node. The algorithm can be optimal quorum length, its time complexity is far less than the same optimal the quorum length of LUK algorithm.3.Proposed a dynamic quorum to determine the quorum to initialize the number of nodes and initialize the position of local recursive generation algorithm. By increasing the initialization of the number of nodes, you can reduce the need to find the number of nodes in the calculation of the quorum, Purpose to reduce the time complexity to generate the request sets, in theory, be able to algorithm time complexity is reduced to N(?)/6+N/2+(?)/3. Partial recursive way to ensure that the length of the quorum to reduce the time complexity of the quorum generation algorithm do not significantly increase. LUK algorithm to generate the quorum generated by the new algorithm compared to the length is basically the same.