Research And Implementation Of Distributed Mutual Exclusion Algorithms

Mutual exclusion is an important problem in distributed systems. Distributed mutual exclusion (DME) is described as that only a single process or node can be allowed to get a shared resource termed as a critical section or CS. And distributed mutual exclusion algorithms are employed to solve the problems such as multi-replica consistency, leader election and so on. With the development of computers and networks, many novel distributed systems are presented continuously. According to the respective characteristics of them, distributed mutual exclusion algorithms must be researched in these actual circumstances.The paper introduced the evolution and the current situation of distributed mutual exclusion algorithms in detail. And the characteristics and actions of distributed mutual exclusion objects were analyzed as following. Then several special DME algorithms were proposed according to the analysis.The major contributions of the dissertation are as below:1. The paper analyzed the characters, the actions and so on of distributed mutual objects and proposed an efficient distributed load-balancing scheme based on replicable resource. Usually, isomerous distributed systems brought the varieties to these distributed mutual objects, which restricted the development of the algorithms. In order to solve these problems, the paper analyzed the characteristics of distributed mutual objects, introduced their influence on DME algorithms and proposed optimal mutual exclusion schemes. Then in this paper, an efficient distributed load-balancing scheme based on replicable resource was proposed. Instead of those traditional schemes, the paper proposed a novel scheme to classify the load of a system as exterior load, interior load and transmission load to be processed respectively. In addition, the paper presented a new conception of load directivity and utilized it in load balancing scheme. At last, the paper presented some stimulation results based on the scheme. And the scheme can efficiently balance load, decrease interior communication flux and restrain system threshing.2. The paper analyzed the circumstances in which DME algorithms were executed. And several Quorum DME algorithms were presented based on special topologies. DME algorithms need to be executed in multi-hop networks and so on. But traditional DME algorithms are usually based on a hypothesis that they can be executed in a fully connected network, which restricts the performance of them. In order to deal these problems, the paper optimized the Quorum structures in DME algorithms according the special network topologies. And the major contributions of the section were as following. (1) Half Quorum algorithm based on linear topologies; (2) Trace Quorum algorithm based on tree topologies. (3) Half-ring Quorum algorithm based on ring topologies; (4) Cross Quorum algorithm on mesh topologies, These DME algorithms have low message complexity, short response delay and good fault-tolerance. Due to the basis of overlay networks, P2P systems don't take account of actual network topologies. So a novel DHT (Distributed Hash Table) DME algorithm were proposed for them.3. The paper proposed an Ad hoc DME algorithm and employed it to solve the LE (Leader Election) problem. Dynamic topologies and mobility brought many difficulties to the implementation of Ad hoc leader election algorithms. Based on the research of the properties of Ad hoc systems and of the previous algorithms, an improved Ad hoc system model were given and a novel algorithm was presented as ADLE (Ad hoc Distributed Leader Election), which was employed in the self-resume landmine field systems. In addition, a generation method was researched to get respective identifiers for DME objects. In addition, ADLE restricted CS executing ranges to decrease the message complexity and synchronous delay of multi-hop Ad hoc networks. Lamport's timestamps were improved to ensure the time sequence and to prevent hosts from starvation. And for dynamic request/reply queues, the nodes didn't initially need knowledge of all the others in ADLE algorithm.4. The paper researched the novel DME algorithms to solve the multi-object (CS) DME problem. And it was of importance to deal with multi-object DME in the circumstances, where distributed nodes synchronously needed to enter several critical sections. According to the DME objects, two improved novel multi-CS DME algorithms were presented in the paper.