基于树拓扑网络的分布式互斥算法  

A Novel Distributed Mutual Exclusion Algorithm Based on Tree Topology Networks

作　　者：王莉[1] 

机构地区：[1]西南民族学院现代教育中心,四川成都610041

出　　处：《计算机仿真》2009年第2期143-146,178,共5页Computer Simulation

摘　　要：分布式互斥是分布式系统的重要问题。根据树拓扑网络的特点,提出了新型的分布式互斥算法TNDME。算法的运行范围限制在根节点到请求节点之间,采用循径方法生成分布式互斥仲裁集;采用Lamport逻辑时戳保证消息的时序性;算法采用"最大残存树"探测方法进行系统的容错处理。描述了算法的模型、主要思想、数据结构、消息结构以及伪代码,并证明了算法的正确性。理论性能分析与仿真对比证明,算法具有较低的消息复杂度、较短的响应延迟以及较好的容错性能。Distributed Mutual Exclusion （DME） is an important problem of distributed systems. According to the properties of tree network systems, a novel algorithm TNDME was presented for them. Based on the node sets between the root and the requestors, the algorithm generated distributed mutual exclusion quorums by trace methods. And Lamport＇s logical timestamps were utilized to guarantee the time sequence. Furthermore, ＂Max Remainder Tree＂ probe methods were employed to implement the fault - tolerance of the algorithm. The algorithm model, the main idea, the data structures, the messages and the codes are described respectively. Performance analysis and simulation results show that it has lower message complexities, shorter response delay and better fairness than the traditional algorithms.

关 键 词：分布式互斥 树网络 循径 仲裁集 

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