Abstract: It is necessary to generate the quorums as soon as possible in large-scale fully distributed system for its mutual exclusion problem. Based on the theory of relaxed cyclic difference set, the definition of second relaxed cyclic difference set was proposed. After researching the new concepts, the subtraction steps in previously classical methods can be changed into summation steps. Furthermore, a lot of summation steps can be cut down by the recurrence relation deduced from the summation steps. The time complexity of this algorithm is just only O(n) and the size of the symmetric quorums is still close to 2n^(1/2).

Key words: distributed mutual exclusion, quorum, relaxed cyclic difference, time complexity

摘要： 在大规模完全分布式系统的互斥问题上，快速生成请求集是必要的。在基于松弛差集的相关原理上，引入了二次松弛差集的概念。经分析相关概念及定理，将原本“求差”的过程变为“求和”的过程;进而利用 “求和”步骤间的递推关系，大大减少了求和步骤，使整个算法的时间复杂度控制在O(n)。与时间复杂度同为O(n^2)的其他经典算法相比，生成的请求集长度仍保持在2n^(1/2)的数量级。

关键词: 分布式互斥, 请求集, 松弛差集, 时间复杂度