具有O(n)时间复杂度的分布式请求集生成算法

Quorum generation algorithm with time complexity of O(n)

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

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 2√n.