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

摘要

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