基于局部递归的动态多点初始化请求集生成算法

doi:10.3724/SP.J.1087.2012.00606

计算机应用 ›› 2012, Vol. 32 ›› Issue (03): 606-608.DOI: 10.3724/SP.J.1087.2012.00606

基于局部递归的动态多点初始化请求集生成算法

李美安,林岚,陈志党

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

收稿日期:2011-09-26 修回日期:2011-12-18 发布日期:2012-03-01 出版日期:2012-03-01
通讯作者: 李美安
作者简介:李美安(1973-),男,四川大竹人,教授,博士,主要研究方向:分布式操作系统、分布式算法;林岚(1988-),女,广东肇庆人,硕士研究生,主要研究方向:分布式操作系统、分布式算法;陈志党(1985-),男,安徽砀山人,硕士研究生,主要研究方向:分布式操作系统、分布式算法。
基金资助:
国家自然科学基金资助项目(61063004)。

Quorum generation algorithm of dynamic and multi-node initiation based on local recursion

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

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

Received:2011-09-26 Revised:2011-12-18 Online:2012-03-01 Published:2012-03-01
Contact: Mei-An LI

摘要/Abstract

摘要： 如何在保证请求集长度不显著增加的情况下使时间复杂度尽量减小,是对称分布式互斥请求集生成算法研究者必须解决的问题。通过动态增加初始化节点的方法,采用局部递归的方式设计了一种新的对称分布式互斥请求集生成算法。该算法能够保证请求集长度与其长度下限比较不会显著增加,而时间复杂度比WK算法及全局递归算法有显著下降。因此,通过对请求集本身特性的研究,能够部分解决请求集长度与请求集生成算法时间复杂度之间的矛盾。

关键词: 动态初始化, 局部递归, 请求集, 生成算法

Abstract: How to reduce the time complexity of the quorum generation algorithm effectively when the quorum length does not increase significantly is a question must be resolved to all researchers of symmetric quorum generation algorithm for distributed mutual exclusion. A new quorum generation algorithm was proposed in this paper by adopting the local recursion. This algorithm can reduce the time complexity of the quorum generation algorithm effectively and ensure the quorum length not increasing significantly than WK's algorithm and global recursion algorithm. Therefore, through researching the features of quorum, the contradiction between quorum length and time complexity of the quorum generation algorithm can be improved.

Key words: dynamic initiation, local recursion, quorum, generation algorithm

中图分类号:

李美安林岚陈志党. 基于局部递归的动态多点初始化请求集生成算法[J]. 计算机应用, 2012, 32(03): 606-608.

LI Mei-an LIN Lan CHEN Zhi-dang. Quorum generation algorithm of dynamic and multi-node initiation based on local recursion[J]. Journal of Computer Applications, 2012, 32(03): 606-608.

参考文献

[1]NG W K, RAVISHANKAR C V. Coterie templates: A new quorum construction method [C]// Proceedings of the 15th International Conference on Distributed Computing Systems. Piscataway, NJ: IEEE Press,1995:92-99.

[2]LI MEIAN, LIU XINSONG, WANG ZHENG, et al. A symmetric quorum algorithm for distributed mutual exclusion based on cyclic coding and the properties of cyclic quorum [J]. Chinese Journal of Electronics, 2006,15(1):17-20.

[3]李美安,刘心松,王征.一种基于循环编码的高性能分布式互斥算法[J].电子学报,2005,33(8):1397-1402.

[4]李美安,刘心松,王征。一种基于松弛循环差集的高性能分布式互斥算法[J].电子学报,2007,35(1):58-63.

[5]LI MEIAN, ZHAN JUNWEI, PEI XICHUN. A variable-length quorum generation algorithm for distributed mutual exclusion [C]// Proceedings of 2010 International Conference on Multimedia Technology. Piscataway, NJ: IEEE Press, 2010: 1943-1946.

[6]LI MEIAN, WANG BUYU, LI WEI, et al. A wrong opinion about quorum generation algorithm for distributed mutual exclusion [C]// Proceedings of International Conference on Apperceiving Computing and Intelligence Analysis. Piscataway, NJ: IEEE Press, 2009:97-100.

[7]陈志党,李美安,战俊伟,等.一种新的分布式互斥请求集生成算法[J].微计算机信息, 2010,26(9):211-212.

[8]武鹏,李美安,裴喜春,等.改进的分布式互斥请求集生成算法[J].计算机应用,2010,31(S1):243-245.

[9]郭玉波,陈志党,王春申,等.一种高效能的分布式请求集生成算法[J].微计算机信息,2011,27(8):201-203.

[10]张娜,郑骏.基于三角网格请求集的动态位置管理算法[J].计算机工程,2007,33(22):145-147.

[11]李美安,陈志党,王春申,等.基于贪心策略的高效能分布式请求集生成算法[J].计算机应用研究,2011,28(7):2522-2524.

基于局部递归的动态多点初始化请求集生成算法

Quorum generation algorithm of dynamic and multi-node initiation based on local recursion

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

[1]	张永斌, 常文欣, 孙连山, 张航. 基于字典的域名生成算法生成域名的检测方法[J]. 计算机应用, 2021, 41(9): 2609-2614.
[2]	周玉瀚, 韩国栋, 沈剑良, 姜奎. 基于Rent规则的片上网络局部化特性流量生成算法[J]. 计算机应用, 2016, 36(5): 1206-1211.
[3]	刘恒李美安苏萌. 基于重复数的最短循环请求集生成算法[J]. 计算机应用, 2014, 34(5): 1263-1266.
[4]	武鹏李美安. 具有O(n)时间复杂度的分布式请求集生成算法[J]. 计算机应用, 2013, 33(02): 323-360.
[5]	王刚孙济洲李文. 一种启发式双代号网络图自动生成算法[J]. 计算机应用, 2007, 27(3): 762-764.
[6]	张庆丰，周继鹏. 一种快速直线脉冲增量插补算法[J]. 计算机应用, 2005, 25(06): 1420-1421.