一种基于松弛循环差集的对称分布式互斥算法

A Symmetric Distributed Mutual Exclusion Algorithm Based on Relaxed Cyclic Difference Set

为在全分布系统中实现对称的分布式互斥,需要设计出对称的分布式互斥算法。通过证明循环请求集与松弛循环差集的等价性,将求取包含任意数量节点的分布式系统对称请求集的问题转化为求取任意数量节点集合的松弛差集问题,并在此基础上提出了一种基于循环松弛差集的对称分布式互斥请求集生成算法。在请求集生成算法的基础上,引入了转移应答消息和请求集重构消息,重新定义应答消息的结构以使其能够携带更多的信息,重新设计了分布式互斥算法的相关过程,从而改进了Makawa类分布式互斥算法的性能。该算法具有较高的时间效率和空间效率,其求取的请求集尺寸较小,使分布式互斥算法的消息复杂度降为O(2N),同步时间降为T,节点容错能力达到N-1。基于松弛循环差集的分布式互斥算法克服了以往分布式算法必须牺牲一种性能指标以提高另一种性能指标的缺点,具有很高的应用价值。

In fully distributed system, the right and responsibility of sites in the system need to be symmetric. Through proving the equivalence of cyclic quorum to relaxed cyclic difference set, the problem of seeking the symmetric quorum to a system including any number sites was transfered to seeking a relaxed difference set of a system including any number sites. On this basis, a symmetric quorum algorithm was proposed. Based on the quorum algorithm, through introducing the TRANS_ REP message and RECONSTRUCT message,we redefined the data structure of the REPLY message and make it take more information. This quorum algorithm has a higher time efficiency and memory efficiency, and the quorum generated by this algorithm is very small. These methods improved the performance of the Makawa type algorithms and make the message complexity reduce to O （2（N的平方根）） , the synchronization delay reduce to T and the sites fault-tolerance of Makawa type distributed mutual exclusion increase to N - 1 .The distributed mutual exclusion algorithm based on relaxed difference set overcomes the defect of other algorithms which need to reduce some performance indexes to improve some special performance indexes.