DocumentCode
1940686
Title
Message complexity of the tree quorum algorithm for distributed mutual exclusion
Author
Chang, Her-kun ; Yuan, Shyan-Ming
Author_Institution
Dept. of Comput. & Inf. Sci., Nat. Chiao Tung Univ., Hsinchu, Taiwan
fYear
1994
fDate
21-24 Jun 1994
Firstpage
76
Lastpage
80
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
Keywords
communication complexity; distributed algorithms; distributed mutual exclusion; fault-tolerant solution; message complexity; tree quorum algorithm; Binary trees; Distributed computing; Fault tolerant systems; Information science; Permission; Taxonomy; Tree data structures; Voting;
fLanguage
English
Publisher
ieee
Conference_Titel
Distributed Computing Systems, 1994., Proceedings of the 14th International Conference on
Conference_Location
Pozman
Print_ISBN
0-8186-5840-1
Type
conf
DOI
10.1109/ICDCS.1994.302395
Filename
302395
Link To Document