标题: 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
显示于类别:Articles


文件中的档案:

  1. A1995RR69600010.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.