摘要:如何在保证请求集长度不显著增加的情况下使时间复杂度尽量减小,是对称分布式互斥请求集生成算法研究者必须解决的问题。通过动态增加初始化节点的方法,采用局部递归的方式设计了一种新的对称分布式互斥请求集生成算法。该算法能够保证请求集长度与其长度下限比较不会显著增加,而时间复杂度比WK算法及全局递归算法有显著下降。因此,通过对请求集本身特性的研究,能够部分解决请求集长度与请求集生成算法时间复杂度之间的矛盾。
关键词:动态初始化;局部递归;请求集;生成算法
中图分类号: TP301.6;TP316.4文献标志码:A
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)
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
0引言
近年来,分布式计算、网格计算、云计算等先进计算模型与技术不停地被提出和改进,各种基于网络互联技术和资源共享技术的虚拟计算系统也不停地被推向市场。但是,不管哪种先进计算模型,其基础都是基于分布式互斥的资源共享技术。高效、对称、没有死锁的分布式互斥算法是分布式互斥技术的核心。而高效、对称、没有死锁,正是基于竞争的分布式互斥算法被提出的目的。基于竞争的分布式互斥算法的核心,是对称分布式互斥请求集。分布式互斥请求集的对称性决定了分布式互斥算法的对称性,分布式互斥请求集的长度决定了分布式互斥算法的消息复杂度和效率,分布式请求集生成算法的时间复杂度决定了分布式互斥算法所能适应的分布式系统的规模。
如何设计出请求集长度短(极度接近对称分布式请求集长度下限),时间复杂度低(远低于WK算法[1])的分布式互斥请求集生成算法,是近年来分布式互斥研究领域的热点。由于对称分布式互斥请求集的长度与分布式互斥请求集生成算法的时间复杂度之间具有不可调和的矛盾,人们在研究对称分布式请求集生成算法时,总会采取牺牲一方面的性能以换取另一方面性能的改善,如文献[2-6],特别是为了减少请求集生成算法的时间开销和降低实现难度,人们总是在不限定请求集长度的情况下按一定算法的贪心策略来生成请求集,如文献[7-11]。由于没有考虑请求集中节点的全局分布,因此找到的请求集长度总是接近2N。因此当前已有的对称分布式互斥请求集生成算法总是不能同时达到请求集长度最短、时间复杂度最低的目的。
为了满足请求集长度短、时间复杂度低的要求,本文提出了基于局部递归的动态多点初始化请求集生成算法,它具有时间复杂度低、请求集长度短的特性,基本解决了目前请求集生成算法设计的困境。
1系统模型
设系统节点数为N,并按0到N-1设定节点的序号。每个节点的请求集用一个长度为N的向量表示。该向量称之为该节点的请求集向量(Quorum),简称节点的请求集。请求集向量是一个0-1向量。该向量的元素代表相应的节点,元素的下标代表节点的序号。元素值为1的位置表示代表该元素位置的节点包含于请求集,值为0表示代表该元素位置的节点不包含于请求集。用k表示当前请求集中节点的数量,即请求集长度。
2算法描述
2.1算法原理
在分布式系统中选择k个节点作为备选请求集,这k个节点的组合称为k-节点组合。求k-节点组合的差集,测试差集是否覆盖了系统所有节点的过程,称为k-节点组合的覆盖测试。在本文算法中以生成表示状态数组来实现覆盖测试。在求取系统的请求集的过程中,如果把所有未进入请求集的节点都当作可选节点测试请求集是否存在,称该请求集生成算法为全局递归算法或完全递归算法。如果只对未被覆盖或表示的节点测试请求集是否存在,则称该请求集生成算法为局部递归算法。
在对请求集进行初始化时,为了减小请求集的长度,要求初始化节点之间形成的差集元素尽量不要重复。根据这种要求,一般可采取初始化请求集向量的mn-1的位置节点的方式完成初始化。其中m为大于1的整数,n是从0开始的自然数。这主要是因为n1和n2为任意值时mn1-mn2的值都不会重复。为尽量增加初始化节点数量,降低请求集生成算法的时间复杂度,且避免差集元素的重复,本文算法采用2n-1方式初始化请求集的前半部分,初始化的节点数将根据系统长度动态改变。同时本文算法采用局部递归的方式求请求集除初始化节点外的剩余部分。因此称本文算法为基于局部递归的动态多点初始化请求集生成算法。
第3期 李美安等:基于局部递归的动态多点初始化请求集生成算法计算机应用 第32卷2.2数据结构与算法过程
Quorum,为请求集向量,用于记录在请求集生成算法运行结束时生成的请求集。
State,表示状态数组,用于记录当前请求集所能表示或覆盖的所有节点。
Zero,表示状态数组中元素为0的位置组成的向量。
Scope,初始化范围,表示在什么范围内对请求集进行初始化。由于循环请求集的对称性,一般对请求集的前半部分进行初始化。
Search_k(N),寻找N个节点分布式系统的请求集长度下限的过程。
Init(Scope),请求集初始化算法,即采用什么方式对请求集的初始化范围Scope进行初始化。它将直接影响初始化请求集的质量和节点数,对请求集长度也有直接的影响。本文算法采用初始化2n-1位置的方式。
GenerateState(Quorum),表示状态数组生成过程。生成请求集Quorum对应的表示状态数组State向量。
SearchStateZero(State),查找表示状态数组State中未被表示的节点的过程,并将这些节点的ID号放入返回的Zero数组中。
Choise(Zero),在Zero数组中选择一个节点放入请求集Quorum。
Length(Zero),求数组Zero的长度。
Length(Quorum),求数组Quorum的长度,即求Quorum中1的个数。
TestInsert(Quorum,Zero,k),向请求集插入节点过程。用于向请求集中插入节点,也是请求集生成算法递归实现的核心部分。其中k表示当前可纳入请求集的节点数量。
2.3算法描述
2.4算法运行实例
图2是N=15时算法运行过程中请求集的变化情况。从算法运行完成时请求集的内容看,N=15时请求集长度为5,跟WK算法结果相同;节点尝试次数为6,比WK算法少得多。
图片图2N=15时请求集生成过程
3性能分析
3.1平均时间复杂度
根据Makawa算法,设请求集长度下限为N,初始化的节点数为k。则理论上WK算法的时间复杂度为CN-kN-k。由于全局递归算法并不每次都需要对N-k个节点进行尝试,而是只要找到一个符合条件的节点,就结束尝试。因此全局递归算法的时间复杂度小于CN-kN-k。而局部递归算法每次总是在未被表示的节点中选择纳入请求集的节点,而当请求集中包含的节点数为n时,未被表示的节点数的平均值为(n2+n)/2,因此当初始化节点数为1时局部递归算法的时间复杂度为NN/6+N/2+N/3。当初始化节点数大于1时,算法的时间复杂度一定小于NN/6+N/2+N/3。
表1是本文提出的局部递归算法在初始化范围为[0,N/2],采用2n-1初始化算法初始化请求集时与WK算法和全局递归算法在N∈[44,58]范围的尝试比较次数对比。
试次数的比例;比例2表示局部递归算法与全局递归算法的尝试次数的比例。
从表1可看出:比例1的所有值均小于1,并且所有比例1的值都小于等于3%。因此,在N∈[44,58],初始化范围为[0,N/2],采用2n-1的初始化算法的情况下,全局递归算法的时间复杂度确实比WK算法小且全局递归算法的时间复杂度都小于WK算法的5%。因此,在时间复杂度方面全局递归算法在N∈[44,58]时比WK算法至少改善了95%。
从表1还可看出:比例2的值一般都在15%以下,个别情况下为35%左右。因此,局部递归算法较全局递归算法在N∈[44,58],初始化范围为[0,N/2],采用2n-1的初始化算法的情况下时间复杂度改善了60%以上,多数时候其改善在90%左右。
3.2请求集长度
由于本文算法采用了局部递归生成请求集的方式,因此,如果采用的初始化算法及初始化范围对请求集长度没有影响,则请求集长度应与全局递归算法及WK算法基本相同,为N。但如果采用的初始化算法及初始化范围对请求集长度有影响,则请求集长度将大于N。表2是初始化范围为[0,N/2],采用2n-1的初始化算法,在N∈[44,57]时WK算法与全局递归算法和本文采用的局部递归算法请求集长度的比较。
4结语
本文提出了一种动态确定请求集初始化节点数与初始化位置的基于局部递归的循环请求集生成算法,它通过增加初始化节点数量,从而减少在计算请求集时需要寻找的节点数量的方式,来降低生成请求集的时间复杂度,理论上能将算法的时间复杂度降低到NN/6+N/2+N/3。本文还采用局部递归的方式来保证在降低请求集生成算法的时间复杂度时请求集长度不显著增加,从而使得本文算法所生成的请求集与WK算法生成的请求集长度基本相同。因此,采用基于局部递归的动态初始化请求集生成算法,能够达到对称请求集生成算法时间复杂度低、请求集长度短的目的。
参考文献:
[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.