Message complexity of the tree quorum algorithm for distributed mutual exclusion

Her Kun Chang*, Shyan-Ming Yuan

*Corresponding author for this work

Research output: Contribution to conferencePaper

3 Scopus citations

Abstract

The tree quorum algorithm (TQA), which logically organizes the sites in a system into a tree, is an efficient and fault-tolerant solution for distributed mutual exclusion. Quorum size can be reduced to log N in the best case of TQA. In this paper, message complexity of TQA is analyzed. Moreover, it is shown that the ratio of message complexity to quorum size converges to 1/p, where p is the probability that a site is operational.

Original languageEnglish
Pages76-80
Number of pages5
StatePublished - 1 Dec 1994
EventProceedings of the 1994 IEEE 14th International Conference on Distributed Computing Systems - Poznan, Pol
Duration: 21 Jun 199424 Jun 1994

Conference

ConferenceProceedings of the 1994 IEEE 14th International Conference on Distributed Computing Systems
CityPoznan, Pol
Period21/06/9424/06/94

Fingerprint Dive into the research topics of 'Message complexity of the tree quorum algorithm for distributed mutual exclusion'. Together they form a unique fingerprint.

  • Cite this

    Chang, H. K., & Yuan, S-M. (1994). Message complexity of the tree quorum algorithm for distributed mutual exclusion. 76-80. Paper presented at Proceedings of the 1994 IEEE 14th International Conference on Distributed Computing Systems, Poznan, Pol, .