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

A High Performance Distributed Mutual Exclusion Algorithm Based on Cyclic Coding

作　　者：李美安[1] 刘心松[1] 王征[1] 

机构地区：[1]电子科技大学计算机学院8010研究室,四川成都610054

出　　处：《电子学报》2005年第8期1397-1402,共6页Acta Electronica Sinica

摘　　要：公平、健壮和易于实现的分布式互斥算法对分布式系统保证数据一致性、逻辑一致性及时序一致性至关重要.除Lamport算法,RA算法和N0.63算法外,以前提出的分布式互斥算法都只是在节点数目与请求集大小存在一定关系时才是公平和对称的,在大多数情况下是不对称的.这些算法的同步时间,容错性能与消息复杂度之间存在着不可调和的矛盾,不能三者兼顾.本文提出了一种基于循环编码的互斥请求集产生算法,并在此基础上改进了已有的基于请求集的分布式互斥算法,使该算法在系统节点数为任意值时都能公平和对称地产生请求集.其消息复杂度较低,同步时间为T,节点容错能力达到N-1.It＇s very important to use a fair and easy implementation distributed mutual exclusion algorithm to ensure the data, logic and time consistency of a distributed system. Except the Lamport, RA and N^0.63 algorithm,all the other distributed mutual exclusion algorithms brought forward formerly are fair only when the number of the system sites is peculiarly related on the sites number of the quorum. It＇s not fair in most instances. And there are some contradiction in synchronization time, message complexity and fault tolerance. A new distributed mutual exclusion algorithm has been proposed that is based on cyclic coding in this paper. This algorithm can reduce the message complexity to O（2 √N） and is fair to any scale distributed system. And the synchronization time has been reduced to T and the fault sites tolerance can be N- 1.

关 键 词：循环编码 分布式 互斥 

分 类 号：TP93[自动化与计算机技术]