| In the problem of mutual exclusion, concurrent access to a shared resource using a structural program abstraction called a Critical Section (CS) must be synchronized such that at any time only one process can enter the CS. In centralized computer systems, the mutual exclusion problem can be easily solved by using shared variables. In distributed systems, due to the lack of 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.;Distributed mutual exclusion algorithms can be classified into two classes: token-based and non-token-based. Depending on the network topology and the information about the search for the token, token-based algorithms can be classified into three approaches: the broadcast approach, the directed edge approach and the request forwarding approach. Depending on how a request set (which is used to record the identifiers of the sites to which a requesting site sends CS request messages when requesting the CS) is formed, non-token-based algorithms can be classified into two approaches: the site-locking approach and the non-site-locking approach.;The major contribution of this research is to propose six new distributed mutual exclusion algorithms which have high performance and can provide a high degree of fault tolerance. Moreover, we study the performance of several well-known distributed mutual exclusion algorithms and compare the performance of our new algorithms and these well-known algorithms.;Based on the token-based broadcast approach, we propose a dynamic token-based distributed mutual exclusion algorithm. Based on the token-based directed edge approach, we propose a token-based distributed mutual exclusion algorithm which is fault-tolerant with respect to communication link and site failures. Based on the token-based request forwarding approach, we propose an improved O(log N) token-based distributed mutual exclusion algorithm, where N is the number of the sites in the system. We give a counterexample to show that Maekawa's O($sqrt{N}$) algorithm, which was the first to use the non-token-based site-locking approach, does not detect and resolve all deadlocks due to some inappropriately deferred messages. We also give a correction to this algorithm. Moreover, based on the non-token-based site-locking approach, we propose a deadlock-free O($sqrt{N}$) distributed mutual exclusion algorithm. Since most distributed mutual exclusion algorithms reduce message traffic by increasing time delay, we propose a hybrid approach to distributed mutual exclusion to minimize both message traffic and time delay at the same time. |
