计算机应用 ›› 2013, Vol. 33 ›› Issue (02): 323-360.DOI: 10.3724/SP.J.1087.2013.00323

• 先进计算 • 上一篇    下一篇

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

武鹏1,李美安2   

  1. 1. 山西工程职业技术学院 计算机工程系，太原 030009
    2. 内蒙古农业大学 计算机与信息工程学院，呼和浩特 010018
  • 收稿日期:2012-08-29 修回日期:2012-10-22 出版日期:2013-02-01 发布日期:2013-02-25
  • 通讯作者: 武鹏
  • 作者简介:武鹏(1981-)，男，山西太原人，助教，硕士，主要研究方向：分布式系统;
    李美安(1973-)，男，四川大竹人，教授，博士，主要研究方向：分布式操作系统、分布式算法。

Quorum generation algorithm with time complexity of O(n)

WU Peng1,LI Meian2   

  1. 1. Department of Computer Engineering, Shanxi Engineering Vocational College, Taiyuan Shanxi 030009, China
    2. College of Computer and Information Engineering, Inner Mongolia Agriculture University, Hohhot Inner Mongolia 010018, China
  • Received:2012-08-29 Revised:2012-10-22 Online:2013-02-01 Published:2013-02-25
  • Contact: WU Peng

PDF

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

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

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

中图分类号: 

版权所有 © 2021 四川计算机应用杂志社有限公司
蜀ICP备 05010208 号-3　新出网证(川)字026号
技术支持：北京玛格泰克科技发展有限公司
访问总数：
今日访问：