A Simulation Study on Distributed Mutual Exclusion

In the problem of mutual exclusion, concurrent access to a shared resource using a structural program abstraction called acritical section(CS) must be synchronized such that at any time only one process can enter the CS. In a distributed system, due to the lack of both a shared memory and a global clock, and due to unpredictable message delay, the design of a distributed mutual exclusion algorithm that is free from deadlock and starvation is much more complex than that in a centralized system. Based on different assumptions about communication topologies and a widely varying amount of information maintained by each site about other sites, several distributed mutual exclusion algorithms have been proposed. In this paper, we suvrey and analyze several well-known distributed mutual exclusion algorithms according to their related characteristics. We also compare the performance of these algorithms by a simulation study. Finally, we present a comparative analysis of these algorithms.     

分布式系统进程互斥算法的研究与改进

本文分析比较了传统互斥算法，提出了一种新的基于令牌的算法，并详细阐述算法的设计思想及其数据结构。本算法最主要的特点是在分布式互斥中引入了优先级和树的概念，能有效的降低进程问的通信量，以及保证互斥和预防死锁。     

Using Logical Rings to Solve the Distributed Mutual Exclusion Problem with Fault Tolerance Issues

In this paper, we investigate distributed mutual exclusion algorithms and delineate the features of a new distributed mutual exclusion algorithm. The basis of the algorithm is the logical ring structure employed in token-based mutual exclusion algorithms. Specifically, there exists dynamic properties of the logical ring that, given certain restrictions regarding message traffic flow, passively give useful information about the location of the token. Effectively, the algorithm demonstrates a type of intelligent routing that identifies useful shortcuts in the routing of the token. The result is a reduction in the total number of messages exchanged prior to the execution of the critical section as compared to the algorithm proposed by Fu and Tzeng [3]. Furthermore, the algorithm allows for an increased degree of fairness in a lightly loaded system than that allowed by Fu and Tzeng's algorithm. The paper also addresses failure recovery issues.     

A New Link Failure Resilient Priority Based Fair Mutual Exclusion Algorithm for Distributed Systems

This paper aims towards designing a new token-based mutual exclusion algorithm for distributed systems. In some of the earlier work, token based algorithms for mutual exclusion are proposed for the distributed environment assuming inverted tree topology. In a wireless setup, such a stable, hierarchical topology is quite unrealistic due to frequent link failures. The proposed token-based algorithm works for processes with assigned priorities on any directed graph topology with or without cycles. The proposed algorithm, in spite of considering priorities of processes, ensures liveness in terms of token requests from low priority processes. Moreover, the algorithm keeps control message traffic reasonably low. The simulation results exhibit the performance of the proposed algorithm under varied contexts besides presenting a comparative performance with other recent algorithms for mutual exclusion like FAPP (Fairness Algorithm for Priority Process).     

分布式互斥算法的研究与改进

在几种基于令牌算法的基础上,提出了一个对网络逻辑结构无要求的分布式互斥算法。算法不但能够在逻辑结构无要求的计算机网络中通过发送消息和传递令牌来同步对临界资源的访问,而且可以很好地解决请求丢失、令牌丢失等问题。通过对算法的性能进行分析验证了该算法是高效的,并给出了正确性证明。     

A Token-Based Fault-Tolerant Distributed Mutual Exclusion Algorithm

In this paper, we propose a token-based distributed mutual exclusion algorithm that is resilient to site and communication failures. The protocol uses the notion of logical time to detect the loss of the token and to recover the state of the lost token. Unlike other approaches, this results in the integration of token recovery due to failures with the protocol itself. Thus, we eliminate the need for expensive election protocols that are generally used in token-based algorithms to regenerate lost tokens. We also introduce the notion of weakly consistent replicated queues that are used to ensure freedom from starvation.     

一种基于令牌的新的互斥算法分析与设计

在对现有典型分布式系统中互斥算法研究的基础上, 本文依据令牌技术, 提出了一种分布式系统中解决互斥问题的新算法.文中对算法的设计思想及实现过程进行了详细描述, 同时对其性能进行了严格的理论证明和分析, 该算法能有效地提高系统的通信效率.     

分布式系统进程互斥算法的研究与改进

随着网络技术的不断发展,分布式系统得到了广泛的研究与应用。然而由于分布式系统中网络带宽有限,且临界资源的数目是固定的,因此研究设计网络负载轻、临界资源利用率高的分布式互斥算法具有重要的意义。文中首先介绍了几种传统的互斥算法,对各个算法的性能加以比较,结合上述分析提出了一种新的基于令牌的算法,并详细阐述算法的设计思想及其数据结构。该算法最主要的特点是在分布式互斥中引入了优先级和选举算法的概念,能有效提高进程间的通信效率。     

一种新的分布式互斥请求集生成算法

分布式互斥请求集的长度、对称性和生成的难易程度以及生成算法占用的空间及耗费的时间直接影响着基于该请求集的分布式互斥算法的消息复杂度、对称性和算法的应用规模。本文在基于循环编码的分布式互斥请求集生成算法的基础上,提出了一种增加算法初始化节点数量的对称分布式互斥请求集生成算法。其生成的请求集长度小于2N0.5,其时间复杂度也比基于循环编码的分布式互斥请求集生成算法小。因此,该算法较已有的分布式互斥请求集生成算法在性能上具有较大提高。     

基于网格网络的十字仲裁集互斥算法

分布式互斥是网格分布式系统的重要问题.根据网格系统的特点,提出了新型的分布式互斥算法.该算法基于网格网络的行列生成分布式互斥十字仲裁集;采用Lamport逻辑时戳保证消息的时序性;算法采用"探测"消息进行系统的容错处理.分析与仿真证明,该算法具有较低的消息复杂度、较短的响应延迟以及较好的容错性能.     

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

分布式互斥是环网分布式系统的重要问题.根据此类系统的特点,提出了新型的分布式互斥算法.该算法以请求者自身为中心,基于半环生成分布式互斥仲裁集;采用Lamport逻辑时戳保证消息的时序性;算法采用"探测"消息进行系统的容错处理.分析与仿真证明,该算法具有较低的消息复杂度、较短的响应延迟以及较好的容错性能.     

自适应Ad hoc分布式互斥算法

Ad hoc网络的动态拓扑结构和节点自组织给分布式算法的实现带来了诸多困难.针对Ad hoc分布式互斥算法研究滞后的现状,提出了一种自适应的Ad hoc分布式算法ADMUTEX. ADMUTEX算法基于令牌查询方法,它采用Lamport逻辑时戳保证消息的时序性,避免了节点饿死.同时,它在消息复杂度与同步延迟之间作了折衷,而且它不需要节点了解系统的全局信息,能够适应Ad hoc网络的动态拓扑结构和节点频繁出入的情况.分析与仿真结果表明该算法具有较低的消息复杂度、小响应延迟和公平性.     

A Token-Based Distributed Group Mutual Exclusion Algorithm with Quorums

The group mutual exclusion problem is a generalization of mutual exclusion problem such that a set of processes in the same group can enter critical section simultaneously. In this paper, we propose a distributed algorithm for the group mutual exclusion problem in asynchronous message passing distributed systems. Our algorithm is based on tokens, and a process that obtains a token can enter critical section. For reducing message complexity, it uses coterie as a communication structure when a process sends a request messages. Informally, coterie is a set of quorums, each of which is a subset of the process set, and any two quorums share at least one process. The message complexity of our algorithm is $O(|Q|)$ in the worst case, where $|Q|$ is a quorum size that the algorithm adopts. Performance of the proposed algorithm is presented by analysis and discrete event simulation. Especially, the proposed algorithm achieves high concurrency, which is a performance measure for the number of processes that can be in critical section simultaneously.     

Empirical Evaluation of Mutual Exclusion Algorithms for Distributed Systems

Mutual exclusion in distributed memory systems is realized by passing messages among sites to establish a sequence for the waiting sites to enter the critical section. We have evaluated various distributed mutual exclusion algorithms on the IBM SP2 machine and the Intel iPSC/860 system, with their empirical results compared in terms of such criteria as the number of message exchanges and response time. The results take into account the effects of critical section request rate, critical section duration, and system size. Our results indicate that the Star algorithm (1991, M. L. Neilsen and M. Mizuno, in “Proc. 11th Int. Conf. Distributed Computing Systems,” pp. 354–360) achieves the shortest response time in most cases among all the algorithms on a small to medium-sized system, when sites request the critical section many times before involving any barrier synchronization. This is because (1) it requires the exchange of no more than three messages per critical section entry, and (2) contention can quickly be alleviated after several entries into the critical section, if no barrier synchronization is involved in the meantime. On the other hand, if every site enters the critical section only once before encountering a barrier, the improved Ring algorithm (1995, S. S. Fu and N.-F. Tzeng, “Efficient Token-Based Approach to Mutual Exclusion in Distributed Memory Systems,” Tech. Rep. TR-95-8-1, CACS, Univ. Southwestern Louisiana, Lafayette) is found to outperform others under a heavy load; but the Star algorithm and the CSL algorithm (1990, Y. I. Chang, M. Singhal, and M. T. Liu, in “Proc. 1990 Int. Conf. Parallel Processing,” Vol. III, pp. 295–302) prevail when the request rate becomes light. The best solution to mutual exclusion in distributed memory systems is determined by how participating sites generate their mutual exclusion requests.     

基于直径仲裁集的网格网络分布式互斥算法

分布式互斥是网格分布式系统的重要问题。根据网格系统的特点,提出了新型的分布式互斥算法。该算法基于网格网络的直径生成分布式互斥仲裁集;采用Lamport逻辑时戳保证消息的时序性;算法采用“探测”消息进行系统的容错处理。分析与仿真证明,该算法具有较低的消息复杂度、较短的响应延迟以及较好的容错性能。     

基于优先级组的分布式互斥算法的改进

主要介绍了一种分布式互斥算法的改进方案,首先简要介绍了基于权标的常规算法,然后提出了优先级组算法的另一种方案,并详细阐述算法的设计思想及其数据结构,本算法最主要的特点是在分布式互斥中引入了优先级和树的概念,从而将Raymond和Ricart_Agrawala互斥算法较好地结合了起来。     

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

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

A Log (N) Distributed Mutual Exclusion Algorithm Based on Path Reversal

In this paper, we present a distributed algorithm for mutual exclusion based on path reversal. The algorithm does not use logical clocks to serialize the concurrent events, and all the variables are bounded. When a process invokes a critical section, it sends a request to the tail of a queue. A dynamical rooted tree gives the path to this tail. The algorithm requires onlyO(log(n)) messages on average, wherenis the number of processes in the network. The performance analysis of the algorithm is based on generating formal power series.