The Average Message Complexity Analysis for Different Distributed Mutual Exclusion Site-tolerant Ways

Many schemes have been proposed to implementation the distributed mutual exclusion. All those algorithms or schemes can be dived into two types based on the fault-tolerant operation. To any type algorithm, the size of the intersection of any two quorums will impact the number of average messages exchanged per Critical Section (CS) execution importantly if the sites are not always operational. In this paper, Basing on the discussions about the average messages in different cases of different algorithms, we get the average messages in the two types algorithm have the same monotony properties to k. and when N and k are all constants, the average messages functions are monotony descend to p. The average messages are more when k=1 than k=N if p is small enough. The minimum of the average messages is M = 3-root N When p=1.