Message complexity of the tree quorum algorithm

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 (½<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