摘要: 在大规模完全分布式系统的互斥问题上,快速生成请求集是必要的。在基于松弛差集的相关原理上,引入了二次松弛差集的概念。经分析相关概念及定理,将原本“求差”的过程变为“求和”的过程;进而利用 “求和”步骤间的递推关系,大大减少了求和步骤,使整个算法的时间复杂度控制在O(n)。与时间复杂度同为O(n^2)的其他经典算法相比,生成的请求集长度仍保持在2n^(1/2)的数量级。
中图分类号:
武鹏 李美安. 具有O(n)时间复杂度的分布式请求集生成算法[J]. 计算机应用, 2013, 33(02): 323-360.
WU Peng LI Meian. Quorum generation algorithm with time complexity of O(n)[J]. Journal of Computer Applications, 2013, 33(02): 323-360.