作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2012, Vol. 38 ›› Issue (14): 59-61. doi: 10.3969/j.issn.1000-3428.2012.14.017

• 软件技术与数据库 • 上一篇    下一篇

基于折半加一的分布式循环请求集生成算法

李美安,林 岚,陈志党   

  1. (内蒙古农业大学计算机与信息工程学院,呼和浩特 010018)
  • 收稿日期:2011-08-11 出版日期:2012-07-20 发布日期:2012-07-20
  • 作者简介:李美安(1973-),男,教授、博士,主研方向:分布式操作系统,分布式计算;林 岚、陈志党,硕士研究生
  • 基金资助:
    国家自然科学基金资助项目“正则图控制数精确解及其相关问题研究”(61063004)

Distributed Cyclic Quorum Generation Algorithm Based on Binary Plus One

LI Mei-an, LIN Lan, CHEN Zhi-dang   

  1. (College of Computer and Information Engineering, Inner Mongolia Agriculture University, Hohhot 010018, China)
  • Received:2011-08-11 Online:2012-07-20 Published:2012-07-20

摘要: 提出一种新的分布式互斥循环请求集生成算法。该算法采用折半加一与局部递归的方式,在不明显增加请求集长度的情况下,能至少降低WK算法50%的时间复杂度。在利用局部递归方式计算循环请求集时,如果系统节点数属于某分段的后半段,则设定其循环请求集长度下限为 +1。性能分析结果表明,该算法能够在规定时间内计算大规模分布式系统的循环请求集,具有较高的实用性。

关键词: 折半加一, 循环请求集, 生成算法, 时间复杂度, 空间复杂度

Abstract: A new distributed cyclic quorum generation algorithm is proposed. Using local recursion and binary plus one, in case of not decreasing quorum length, this algorithm can reduce the time complexity of WK algorithm 50% at least. If the system scale is belong of the behind part in a section, set the shortest quorum length as +1 when using recursion to search quorum. Performance analysis results show that the algorithm can calculate the cyclic quorum of a more large-scale distributed system. So it has higher practicability.

Key words: binary plus one, cyclic quorum set, generation algorithm, time complexity, space complexity

中图分类号: