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

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

作　　者：李美安[1] 林岚[1] 陈志党[1] 

机构地区：[1]内蒙古农业大学计算机与信息工程学院,呼和浩特010018

出　　处：《计算机应用》2012年第3期606-608,共3页journal of Computer Applications

基　　金：国家自然科学基金资助项目(61063004)

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

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TP316.4[自动化与计算机技术—计算机科学与技术]