改进的分布式互斥请求集生成算法

Improved quorum generating algorithm for distributed mutual exclusion

在分布式系统中,各节点必须互斥地访问临界区。节点的请求集的长度决定了系统的效率、性能。虽然最优请求集的节点数最少(大约槡n),但已有的解决方案该类问题算法类似于穷举法,随着节点的增加,该方法变得不可计算。提出了一种快速的请求集生成算法,该算法以循环差集请求集生成算法的理论和贪心算法的基本思想为基础,在每次迭代的过程中,选出一个当前条件下最优的节点加入请求集。与其他的方法相比较,该方法能对任意给定的整数快速、有效地生成对称的请求集。本算法时间复杂度为O(n2),生成的请求集长度为槡n～2槡n。

In the distributed system, nodes must access to the critical section in the mutuaUy exclusive way. The necessary number of the messages for accessing to critical section is determined by the size of quorums to a great extent. This paper introduced a new suboptimal algorithm based on greedy strategy for mutual exclusion in distributed systems and posed mathematical conditions which must meet with the greedy strategy during this algorithm executing. With the algorithm, a symmetric quorum set can be fasfly got for arbitrarily given integer n. The size of the symmetric quorums is between √n and 2√n. Compared with the other methods, the proposed quorum algorithm has a higher time efficiency and the quorum generated by this algorithm is very small.