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

分布式互斥是分布式系统的重要问题.根据树拓扑网络的特点,提出了新型的分布式互斥算法TNDME.算法的运行范围限制在根节点到请求节点之间,采用循径方法生成分布式互斥仲裁集;采用Lamport逻辑时戳保证消息的时序性;算法采用"最大残存树"探测方法进行系统的容错处理.描述了算法的模型、主要思想、数据结构、消息结构以及伪代码,并证明了算法的正确性.理论性能分析与仿真对比证明,算法具有较低的消息复杂度、较短的响应延迟以及较好的容错性能.

A Novel Distributed Mutual Exclusion Algorithm Based on Tree Topology Networks

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. ...