一种基于松弛循环差集的高性能分布式互斥算法  

A High Performance Distributed Mutual Exclusion Algorithm Based on Relaxed Cyclic Difference Set

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

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

出　　处：《电子学报》2007年第1期58-63,共6页Acta Electronica Sinica

摘　　要：基于竞争的分布式互斥算法以请求集为基础.对称的请求集才能产生对称、公平的分布式互斥算法.本文首先证明了循环请求集与松弛循环差集具有等价性,并在此基础上提出了一种基于松弛循环差集的对称请求集生成算法.在提出动态令牌和请求集重构概念的基础上,本文将Maekawa类分布式互斥的同步时间降为T,节点容错能力达到N-1,一次临界区执行所需交换的消息数降为2m-3m,m是请求集大小.A new quorum generation algorithm has been presented.A symmetric quorum can be generated based on this algorithm. And the size of the quorum is about 2 ＊ sqrt（N）. In the basis on the message of transfer, the synchronization delay time of the distributed exclusion has been reduced to T. Through the quorum re-constructing, the sites fault-tolerance of Maekawa type distributed mutual exclusion algorithm has been increased to N - 1. The message number exchanged of the CS execution will be reduced to 2m - 3m,our distributed mutual exclusion algorithm in this paper has reduced the message complexity of Maekawa type distributed mutual exclusion algorithm m messages, m is the quorum size.

关 键 词：松弛循环差集 分布式 互斥 算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]