文档介绍：摘要
在当前分布式互斥请求集生成算法研究中存在算法的对称性和请求集长度不协
调,时间复杂度、空间复杂度与请求集长度不能兼顾的问题,为了解决上述问题本文
主要从以下三个方面进行进一步的探索和研究。
首先,对于分布式互斥算法时间复杂度过高的问题,本文在 Cyclic 算法的基础上,
通过按斐波那契数列、2 的幂次方的方式对节点进行初始化,然后运用循环编码产生
请求集序列,得到改进后算法的请求集长度、时间复杂度和空间复杂度的数量级,进
而和 Cyclic 算法相比较,从而得出改进后算法的优劣。
其次,为了解决分布式互斥算法请求集长度数量级过高的问题,本文通过提高初
始化节点数量和引进贪心算法策略、差集两方面对算法进行改进,经过算法的改进得
到的请求集长度与 LUK 算法、Maekawa 算法的请求集长度进行比较,从而得出改进
后的算法的优劣。
最后,由于在算法中并不能很好的协调请求集长度、时间复杂度和空间复杂度,
使算法的效率最优,为解决上述问题,本文根据分布式互斥算法的特性,通过自定义
数据结构对分布式算法进行优化,并在算法求解的过程中引入最小不相交距离和局部
最优解的概念,来生成请求集序列,经过算法的改进,和 Cyclic 算法相比较,改进后
的算法空间复杂度比较低、同步时间比较短、容错性能高。
关键词:请求集;初始化;循环编码;循环差集;贪心策略
The Further Exploration for the Algorithm About
Distributed Mutual Exclusion Quorum
Abstract
In the algorithm about distributed mutual exclusion quorum, the symmetry of the
algorithm and the length of quorum are not harmonious,plexity, the space
complexity and the length of quorum can't bined problem, in order to solve the
above problems, this paper focuses on the further exploration and research mainly from the
following three aspects in order to solve the above problems.
First, the plexity of the algorithm about distributed mutual exclusion quorum
is paper initiates the node through i Sequence and a power of 2 on the
basis of Cyclic paper gets the improved algorithm quorum length, time
complexity and the order of magnitude of plexity using cycle code produce
quorum pared to Cyclic algorithm, and concluding the advangtage and
disadvangtage of the improved algorithm.
Second,in order to insolve the magnitude of algorithm about distributed mutual
exclusion quorum is much higher, the paper improves the algorithm through increasing the
number of initial node, introducing greedy algorithm and substruct pares
the concluded length of quorum with LUK algorithm and Maekawa paper
concludes that the the advangtage and disadvangtage of the improved algorithm.
Finally,the eff