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

Abstract:

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 When p=1.

• Periodical: Advanced Materials Research (Volumes 171-172)
• Pages: 675-678
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.171-172.675
• Online since: December 2010
• Authors: Mei An Li, Wei Li, Dong Ma
• Keywords: Average Message Complexity, Distributed Mutual Exclusion, Site-Tolerant

References

[1] L. Lamport, Time, Clocks and Ordering of Events in Distributed Systems, Comm. ACM, vol. 21, no. 7, pp.558-565, July (1978).

DOI: 10.1145/359545.359563

[2] Ricart, G. and Agrawala, A. K, An Optimal Algorithm for Mutual Exclusion in Computer Networks, Communications of the ACM, 24 (1), pp.9-17, Jan. (1981).

DOI: 10.1145/358527.358537

[3] M. Maekawa, A Algorithm for Mutual Exclusion in Decentralized Systems, ACM Trans. Computer Systems, May (1985).

[4] Y. -I. Chang and M. Singhal, and M. Liu, A Hybrid Approach to Mutual Exclusion for Distributed Systems, Proc. Ann. Int'l Computer Software and Application Conf., pp.289-294, Oct. (1990).

[5] M. Naimi and M. Trehel, An Improvement of the Log(n) Distributed Algorithm for Mutual Exclusion, Proc. Seventh Int'l Conf. Distributed Computing System, pp.371-375, (1987).

[6] A. Kumar, Hierarchical Quorum Consensus: A New Algorithm for Managing Replicated Data, IEEE Trans. Computers. pp.996-1004, Sept. (1991).

DOI: 10.1109/12.83661

[7] Y. -C. Kuo and S. -T. Huang, A Geometric Approach for Constructing Coteries and k-Coteries, IEEE Trans. Parallel and Distributed Systems, vol. 8, no. 4, pp.402-411, Apr. (1997).

DOI: 10.1109/71.588618

[8] Rangarajan S. and Setia S. ，A Fault-tolerant Algorithm for Replicated Data Management，Parallel and Distributed Systems, IEEE Transactions on , Volume: 6 , Issue: 12 , Dec. 1995，pp.1271-1282.

DOI: 10.1109/71.476168

[9] Guohong Cao and Singhal M., A delay-optimal quorum-based mutual exclusion algorithm for distributed systems, Parallel and Distributed Systems, IEEE Transactions on , Vol. 12 , no. 12 , p.1256 – 1268, Dec. (2001).

DOI: 10.1109/71.970560