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

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

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