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

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-30 出版日期:2014-05-01
通讯作者: 李美安
作者简介:刘恒(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-30 Published:2014-05-01
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]	侯阳张琼赵紫煊朱正宇张晓博. 基于YOLOv5s的复杂场景下高效烟火检测算法——YOLOv5s-MRD[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[2]	张奇业, 曾心蕊. 带高斯核的支持向量数据描述问题的高效积极集法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3808-3814.
[3]	曹晓意罗煦琼李景贺恩锋. 改进人工势场法下的多无人机编队路径规划方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[4]	袁志超杨磊田井林魏晓威李康顺. 面向复杂约束多目标优化问题的双种群双阶段进化算法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[5]	冷琴, 毛政元. 考虑设施规模决策的两级选址-路径优化[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3513-3520.
[6]	彭庆媛, 王晓峰, 王军霞, 华盈盈, 唐傲, 何飞. 可满足性问题相变研究综述[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3503-3512.
[7]	孙仁科, 皇甫志宇, 陈虎, 李仲年, 许新征. 神经架构搜索综述[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 2983-2994.
[8]	孙安泰, 刘烨, 徐冬梅. 多智能体系统的动态面渐近补偿算法[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3151-3157.
[9]	颜超英, 张紫仪, 曲映楠, 李秋禹, 郑地翔, 孙丽珺. 基于联盟链的双向拍卖碳交易[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3240-3245.
[10]	杨志龙邹德旋李灿邵莹莹马乐杰. 融入限制反向学习与柯西-高斯变异的蜣螂优化算法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[11]	姚光磊, 熊菊霞, 杨国武. 基于神经网络优化的花朵授粉算法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2829-2837.
[12]	力尚龙, 刘建华, 贾鹤鸣. 融合多狩猎协调策略的爬行动物搜索算法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2818-2828.
[13]	李焱, 潘大志, 郑思情. 多车场带时间窗车辆路径问题的改良自适应大邻域搜索算法[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1897-1904.
[14]	张倩婷胡丽莹陈黎飞. 时间序列的鲁棒形态表征方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[15]	胡林波倪志伟程家乐刘文涛朱旭辉. 基于融合社区检测的复杂协作众包任务分配方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.

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

Shortest cyclic quorum generation algorithm based on number of repetitions

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics