標題: MESSAGE COMPLEXITY OF THE TREE QUORUM ALGORITHM
作者: YUAN, SM
CHANG, HK
交大名義發表
資訊工程學系
National Chiao Tung University
Department of Computer Science
關鍵字: DISTRIBUTED MUTUAL EXCLUSION;TREE QUORUM ALGORITHM;QUORUM SIZE;MESSAGE COMPLEXITY
公開日期: 1-八月-1995
摘要: The tree quorum algorithm (TQA) uses a tree structure to generate intersecting (tree) quorums for distributed mutual exclusion, This paper analyzes the number of messages required to acquire a quorum in TQA. Let i be the depth of the complete binary tree used in TQA, and let M(i) be the number of messages required to acquire a quorum or to determine that no quorum is accessible. We discuss M(i) as a function of i and p, where p (1/2 < p < 1) is the probability that each site is operational. Let C-i denote the average number of sites in the quorum that TQA finds. The analysis shows that, although both M(i) and C-i increase without bound as i increases, M(i)/C-i approaches to 1+p/p as i increases. According to the result, an approximate close form for M(i) is derived.
URI: http://dx.doi.org/10.1109/71.406969
http://hdl.handle.net/11536/1803
ISSN: 1045-9219
DOI: 10.1109/71.406969
期刊: IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
Volume: 6
Issue: 8
起始頁: 887
結束頁: 890
顯示於類別:期刊論文


文件中的檔案:

  1. A1995RR69600010.pdf