基于重复数的最短循环请求集生成算法

doi:10.11772/j.issn.1001-9081.2014.05.1263

计算机应用 ›› 2014, Vol. 34 ›› Issue (5): 1263-1266.DOI: 10.11772/j.issn.1001-9081.2014.05.1263

基于重复数的最短循环请求集生成算法

刘恒,李美安,苏萌

内蒙古农业大学计算机与信息工程学院，呼和浩特 010018

收稿日期:2013-11-13 修回日期:2013-12-27 出版日期:2014-05-01 发布日期:2014-05-30
通讯作者: 李美安
作者简介:刘恒(1988-)，男，河南开封人，硕士研究生，主要研究方向：云计算；李美安(1973-)，男，四川大竹人，教授，博士，主要研究方向：分布式操作系统、分布式算法；苏萌(1988-)，女，黑龙江牡丹江人，硕士研究生，主要研究方向：软件工程与测试。

Shortest cyclic quorum generation algorithm based on number of repetitions

LIU Heng,LI Meian,SU Meng

College of Computer and Information Engineering, Inner Mongolia Agricultural University, Hohhot Nei Mongol 010018, China

Received:2013-11-13 Revised:2013-12-27 Online:2014-05-01 Published:2014-05-30
Contact: LI Meian

摘要/Abstract

摘要：

在分布式循环请求集长度最短时，针对请求集生成算法的时间复杂度和空间复杂度过高问题，提出了一种基于重复数的最短循环请求集生成算法。算法在基于循环松弛差集的思想上，以当前请求集差集允许的最大重复数作为判断条件，依次向请求集中添加元素。实验结果表明，系统节点数为70到90时，该算法在保证请求集长度最短，且空间复杂度为O(2N)的前提下，使得时间复杂度是穷搜方法的3.6E-03到6.8E-07,降低了最短循环请求集生成算法的时间复杂度。

Abstract:

When the length of the cyclic quorum is the shortest in distributed system, the space complexity and the time complexity of the existing quorum generation algorithm are too high, a new shortest cyclic quorum generation algorithm was presented. Based on the theory of relaxed cyclic difference set, adding elements to the quorum in turn was judged by the condition of maximum allowable number of repetitions. The simulation results show that, when the system node number is 70 to 90, the length of the cyclic quorum is the shortest and the space complexity is O(2n), the time complexity is 3.6E-03 to 6.8E-07 of that of the exhaustive search, and the time complexity of the shortest cyclic quorum generation algorithm is reduced.

中图分类号:

刘恒李美安苏萌. 基于重复数的最短循环请求集生成算法[J]. 计算机应用, 2014, 34(5): 1263-1266.

LIU Heng LI Meian SU Meng. Shortest cyclic quorum generation algorithm based on number of repetitions[J]. Journal of Computer Applications, 2014, 34(5): 1263-1266.

参考文献

［1］LAMPORT L. Time, clocks and the ordering of events in a distributed systems ［J］. Communications of the ACM, 1978,21(7):558-565.
［2］MAEKAWA M. A N algorithm for mutual exclusion in decentralized systems ［J］. ACM Transactions on Computer Systems, 1985,3(2):145-159.
［3］LUK W S, WONG T T. Two new quorum based algorithms for distributed mutual exclusion ［C］// Proceedings of the 17th International Conference on Distributed Computing Systems. Washington, DC: IEEE Computer Society, 1997:100-106.
［4］LI M, LIU X, WANG Z. A symmetric distributed mutual exclusion algorithm based on relaxed cyclic difference set ［J］. Journal of Sichuan University: Engineering Science Edition, 2005,37(4):115-118.(李美安,刘心松,王征.一种基于松弛循环差集的对称分布式互斥算法［J］.四川大学学报:工程科学版,2005,37(4):115-118.)
［5］LI M, LIU X, WANG Z. A high performance distributed mutual exclusion algorithm based on relaxed cyclic difference set ［J］. Acta Electronica Sinica, 2007,35(1):58-63.(李美安,刘心松,王征.一种基于松弛循环差集的高性能分布式互斥算法［J］.电子学报,2007,35(1):58-63.)
［6］WU P, LI M. Quorum generation algorithm with time complexity of O(n) ［J］. Journal of Computer Applications, 2013,33(2):323-325.(武鹏,李美安.具有O(n)时间复杂度的分布式请求集生成算法［J］.计算机应用,2013,33(2):323-325.)
［7］CHEN Z, LI M, ZHAN J, et al. A new distributed mutual exclusion quorum generation algorithm ［J］. Microcomputer Information, 2010,26(9): 211-212.(陈志党,李美安,战俊伟,等.一种新的分布式互斥请求集生成算法［J］.微计算机信息,2010,26(9):211-212.)
［8］CHEN Z, LI M, WANG C, et al. High-performance distributed request set generation algorithm based on difference sets ［J］. Microcomputer & Its Applications, 2011,30(3):46-48.(陈志党,李美安,王春申,等.基于差集的高效能分布式请求集生成算法［J］.微型机与应用, 2011,30(3):46-48.)
［9］LI M, LIN L, CHEN Z. Quorum generation algorithm of dynamic and multi-node initiation based on local recursion ［J］. Journal of Computer Applications, 2012, 32(3): 606-608. (李美安,林岚,陈志党.基于局部递归的动态多点初始化请求集生成算法［J］.计算机应用,2012,32(3):606-608.)
［10］LI M, CHEN Z, WANG C. A greedy strategy for more efficient request set generation algorithm ［J］. Microcomputer & Its Applications, 2011,30(13): 52-54.(李美安,陈志党,王春申.一种贪心策略的更高效的请求集生成算法［J］.微型机与应用,2011,30(13):52-54.)
［11］CAO G, SINGHAL M. A delay-optimal quorum-based mutual exclusion algorithm for distributed systems ［J］. IEEE Transactions on Parallel and Distributed Systems, 2001,12(12):1256-1268.
［12］THIARE O, FALL P A. Using Maekawa's algorithm to perform distributed mutual exclusion in quorums ［J］. Advances in Computing, 2012,2(4):54-59.
［13］NG W K, RAVISHANKAR C V. Coterie templates: a new quorum construction method ［C］// Proceedings of the 15th International Conference on Distributed Computing Systems. Washington, DC: IEEE Computer Society, 1995:92-99.

[1]	雷鹰, 郑万波, 魏嵬, 夏云霓, 李晓波, 刘诚武, 谢洪. 基于概率性能感知演化博弈策略的“云+边”混合环境中任务卸载方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3302-3308.
[2]	乔钢柱, 王瑞, 孙超利. 基于分解的高维多目标改进进化算法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3097-3103.
[3]	平凡, 汤小春, 潘彦宇, 李战怀. 不规则任务在图形处理器集群上的调度策略[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3295-3301.
[4]	邹复民, 罗思杰, 陈志辉, 廖律超. 基于轨迹数据的出租车交接班时空分布识别方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3376-3384.
[5]	肖智豪胡志华朱琳. 求解冷链物流时间依赖型车辆路径问题的混合自适应大邻域搜索算法[J]. 计算机应用, 0, (): 0-0.
[6]	沙林秀，聂凡，高倩，孟号. 基于布朗运动与梯度信息的交替优化算法[J]. 计算机应用, 0, (): 0-0.
[7]	董永峰孙跃华高立超韩鹏季海鹏. 基于改进一维卷积和双向长短期记忆神经网络的故障诊断方法[J]. 计算机应用, 0, (): 0-0.
[8]	李大海刘庆腾艾志刚王振东. 基于动态D向分割和混沌扰动的阴阳对算法[J]. 计算机应用, 0, (): 0-0.
[9]	朱诚潘旭华张勇. 基于趋化校正的哈里斯鹰优化算法[J]. 计算机应用, 0, (): 0-0.
[10]	杨杰张名扬芮晓彬王志晓. 融合节点覆盖范围和结构洞的影响力最大化算法[J]. 计算机应用, 0, (): 0-0.
[11]	汤安迪, 韩统, 徐登武, 谢磊. 混沌精英哈里斯鹰优化算法[J]. 计算机应用, 2021, 41(8): 2265-2272.
[12]	李蒙蒙, 秦伟, 刘艺, 刁兴春. 结合头脑风暴优化的混合蚁群优化算法[J]. 计算机应用, 2021, 41(8): 2412-2417.
[13]	张闻强, 邢征, 杨卫东. 基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题[J]. 计算机应用, 2021, 41(8): 2249-2257.
[14]	张祥飞, 鲁宇明, 张平生. 基于协同进化的约束多目标优化算法[J]. 计算机应用, 2021, 41(7): 2012-2018.
[15]	张萌, 李维华. 用户互动表示下的影响力最大化算法[J]. 计算机应用, 2021, 41(7): 1964-1969.

基于重复数的最短循环请求集生成算法

Shortest cyclic quorum generation algorithm based on number of repetitions

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics