| 一种基于松弛循环差集的高性能分布式互斥算法 |
| |
| 引用本文： | 李美安,刘心松,王征.一种基于松弛循环差集的高性能分布式互斥算法[J].电子学报,2007,35(1):58-63. |
| |
| 作者姓名： | 李美安 刘心松 王征 |
| |
| 作者单位： | 电子科技大学计算机学院8010研究室,四川成都 610054 |
| |
| 摘 要： | 基于竞争的分布式互斥算法以请求集为基础.对称的请求集才能产生对称、公平的分布式互斥算法.本文首先证明了循环请求集与松弛循环差集具有等价性,并在此基础上提出了一种基于松弛循环差集的对称请求集生成算法.在提出动态令牌和请求集重构概念的基础上,本文将Maekawa类分布式互斥的同步时间降为T,节点容错能力达到N-1,一次临界区执行所需交换的消息数降为2m-3m,m是请求集大小.
|
| 关 键 词： | 松弛循环差集 分布式 互斥 算法 |
| 文章编号： | 0372-2112（2007）01-0058-06 |
| 收稿时间： | 2005-02-03 |
| 修稿时间： | 2005-02-032006-09-27 |
A High Performance Distributed Mutual Exclusion Algorithm Based on Relaxed Cyclic Difference Set |
| |
| LI Mei-an,LIU Xin-song,WANG Zheng.A High Performance Distributed Mutual Exclusion Algorithm Based on Relaxed Cyclic Difference Set[J].Acta Electronica Sinica,2007,35(1):58-63. |
| |
| Authors: | LI Mei-an LIU Xin-song WANG Zheng |
| |
| Institution: | 8010.R&D Group,University of Electronic Science and Technology of China,Chengdu,Sichuan 610054,China |
| |
| Abstract: | 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. |
| |
| Keywords: | relaxed cyclic difference set distributed mutual exclusion algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《电子学报》浏览原始摘要信息 |
| 点击此处可从《电子学报》下载免费的PDF全文 |
