基于半环仲裁集的环网分布式互斥算法  

Ring Network Distributed Mutual Exclusion Algorithm Based on Half-ring Quorums

作　　者：王征[1] 刘心松[2] 

机构地区：[1]西南财经大学经济信息工程学院,成都610074 [2]电子科技大学计算机科学与工程学院8010研究室,成都610054

出　　处：《计算机科学》2008年第7期88-90,95,共4页Computer Science

基　　金：四川应用基础研究项目(NO.04JY029-017-2);科技型中小企业技术创新基金(04C26225110223)资助

摘　　要：分布式互斥是环网分布式系统的重要问题。根据此类系统的特点,提出了新型的分布式互斥算法。该算法以请求者自身为中心,基于半环生成分布式互斥仲裁集;采用Lamport逻辑时戳保证消息的时序性;算法采用"探测"消息进行系统的容错处理。分析与仿真证明,该算法具有较低的消息复杂度、较短的响应延迟以及较好的容错性能。Distributed Mutual Exclusion （DME） is an important problem of distributed ring systems. According to the properties of ring networks, a novel algorithm is presented for them. Based on these half-rings,the algorithm generates distributed mutual exclusion quorums and regarded requesters as centers. And Lamport＇s logical timestamps are utilized to guarantee the time sequence. Furthermore,＂Probe＂ messages are employed to implement the fault-tolerance of the algorithm. Analysis and simulation results show that it has lower message complexity; shorter response delay and better fairness than the traditional algorithms do so.

关 键 词：分布式互斥 环网 仲裁集 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论]