Shortest cyclic quorum generation algorithm based on number of repetitions

doi:10.11772/j.issn.1001-9081.2014.05.1263

Journal of Computer Applications ›› 2014, Vol. 34 ›› Issue (5): 1263-1266.DOI: 10.11772/j.issn.1001-9081.2014.05.1263

Previous Articles Next Articles

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

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

刘恒,李美安,苏萌

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

通讯作者: 李美安
作者简介:刘恒(1988-)，男，河南开封人，硕士研究生，主要研究方向：云计算；李美安(1973-)，男，四川大竹人，教授，博士，主要研究方向：分布式操作系统、分布式算法；苏萌(1988-)，女，黑龙江牡丹江人，硕士研究生，主要研究方向：软件工程与测试。

Abstract

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.

摘要：

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

CLC Number:

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.

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

References

［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-MRD: an efficient fire and smoke detection algorithm for complex scenarios based on YOLOv5s [J]. Journal of Computer Applications, 0, (): 0-0.
[2]	Qiye ZHANG, Xinrui ZENG. Efficient active-set method for support vector data description problem with Gaussian kernel [J]. Journal of Computer Applications, 2024, 44(12): 3808-3814.
[3]	. Path planning of multi-UAV formation based on improved artificial potential field method [J]. Journal of Computer Applications, 0, (): 0-0.
[4]	. Dual-population dual-stage evolutionary algorithm for complex constrained multi-objective optimization problems [J]. Journal of Computer Applications, 0, (): 0-0.
[5]	Qin LENG, Zhengyuan MAO. Two echelon location-routing optimization considering facility sizing decision [J]. Journal of Computer Applications, 2024, 44(11): 3513-3520.
[6]	Qingyuan PENG, Xiaofeng WANG, Junxia WANG, Yingying HUA, Ao TANG, Fei HE. Review of phase transition in satisfiability problems [J]. Journal of Computer Applications, 2024, 44(11): 3503-3512.
[7]	Renke SUN, Zhiyu HUANGFU, Hu CHEN, Zhongnian LI, Xinzheng XU. Survey of neural architecture search [J]. Journal of Computer Applications, 2024, 44(10): 2983-2994.
[8]	Antai SUN, Ye LIU, Dongmei XU. Dynamic surface asymptotic compensation algorithm for multi-agent systems [J]. Journal of Computer Applications, 2024, 44(10): 3151-3157.
[9]	Chaoying YAN, Ziyi ZHANG, Yingnan QU, Qiuyu LI, Dixiang ZHENG, Lijun SUN. Double auction carbon trading based on consortium blockchain [J]. Journal of Computer Applications, 2024, 44(10): 3240-3245.
[10]	. Dung beetle optimizer algorithm with restricted reverse learning and Cauchy-Gauss variation [J]. Journal of Computer Applications, 0, (): 0-0.
[11]	Guanglei YAO, Juxia XIONG, Guowu YANG. Flower pollination algorithm based on neural network optimization [J]. Journal of Computer Applications, 2024, 44(9): 2829-2837.
[12]	Shanglong LI, Jianhua LIU, Heming JIA. Reptile search algorithm based on multi-hunting coordination strategy [J]. Journal of Computer Applications, 2024, 44(9): 2818-2828.
[13]	Yan LI, Dazhi PAN, Siqing ZHENG. Improved adaptive large neighborhood search algorithm for multi-depot vehicle routing problem with time window [J]. Journal of Computer Applications, 2024, 44(6): 1897-1904.
[14]	. Robust shapeles representation method for time series [J]. Journal of Computer Applications, 0, (): 0-0.
[15]	HU Linbo , NI Zhiwei , CHENG Jiale, LIU Wentao , ZHU Xuhui , . Complex collaborative crowdsourcing task allocation method based on fusion community detection [J]. Journal of Computer Applications, 0, (): 0-0.

Shortest cyclic quorum generation algorithm based on number of repetitions

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics