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

Quorum generation algorithm with time complexity of O(n)

作　　者：武鹏[1] 李美安[2] 

机构地区：[1]山西工程职业技术学院计算机工程系,太原030009 [2]内蒙古农业大学计算机与信息工程学院,呼和浩特010018

出　　处：《计算机应用》2013年第2期323-325,360,共4页journal of Computer Applications

摘　　要：在大规模完全分布式系统的互斥问题上,快速生成请求集是必要的。在基于松弛差集的相关原理上,引入了二次松弛差集的概念。经分析相关概念及定理,将原本"求差"的过程变为"求和"的过程;进而利用"求和"步骤间的递推关系,大大减少了求和步骤,使整个算法的时间复杂度控制在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.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TP316.4[自动化与计算机技术—计算机科学与技术]