一种基于循环编码的高性能分布式互斥算法

公平、健壮和易于实现的分布式互斥算法对分布式系统保证数据一致性、逻辑一致性及时序一致性至关重要.除Lamport算法,RA算法和N0.63算法外,以前提出的分布式互斥算法都只是在节点数目与请求集大小存在一定关系时才是公平和对称的,在大多数情况下是不对称的.这些算法的同步时间,容错性能与消息复杂度之间存在着不可调和的矛盾,不能三者兼顾.本文提出了一种基于循环编码的互斥请求集产生算法,并在此基础上改进了已有的基于请求集的分布式互斥算法,使该算法在系统节点数为任意值时都能公平和对称地产生请求集.其消息复杂度较低,同步时间为T,节点容错能力达到N-1.