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

Distributed Cyclic Quorum Generation Algorithm Based on Binary Plus One

作　　者：李美安[1] 林岚[1] 陈志党[1] 

机构地区：[1]内蒙古农业大学计算机与信息工程学院,呼和浩特010018

出　　处：《计算机工程》2012年第14期59-61,共3页Computer Engineering

基　　金：国家自然科学基金资助项目"正则图控制数精确解及其相关问题研究"(61063004)

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

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]