标题: | 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 |
文件中的档案:
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.