陈志党，李美安，王春申，林 岚

（内蒙古农业大学 计算机科学与技术学院，内蒙古 呼和浩特 010018）

基于差集的高效能分布式请求集生成算法

陈志党，李美安，王春申，林 岚

（内蒙古农业大学 计算机科学与技术学院，内蒙古 呼和浩特 010018）

松弛正向差集；请求集;折半循环编码算法

基于请求集的分布式互斥算法作为Maekawa算法[1]的推广，近年来得到了人们的广泛关注，人们提出了许多各具特色的算法[2-5]来构建请求集以降低分布式互斥算法的消息复杂度或者提高分布式互斥算法在其他方面的性能。但在通常情况下，分布式互斥请求集生成算法的性能直接影响分布式互斥算法的性能。例如，请求集生成算法的对称性将影响分布式互斥算法的对称性，请求集生成算法所生成请求集的长度直接影响基于其上的分布式互斥算法的消息复杂度。而目前已经存在的分布式互斥请求集生成算法在请求集长度、时间复杂性等方面都不能让人满意。李美安[6]介绍了一种用循环编码产生请求集的互斥算法，它通过循环编码产生请求集的方式得出一种消息复杂度较低、容错性能高且同步时间短的对称分布式互斥算法。但由于李氏循环编码互斥算法的初始化节点数较少，因此算法的时间复杂度还是较高。

1 系统模型

设系统的节点数为 N，并从 0～N-1对节点编号，第i个节点的ID号为i-1，假定系统的节点与通信均可靠，各节点没有共享存储器和共同的物理时钟，节点间依靠消息进行异步通信，并且消息通信时间延迟无法预知。……