MESSAGE COMPLEXITY OF THE TREE QUORUM ALGORITHM

The tree quorum algorithm (TQA) uses a tree structure to generate inte rsecting (tree) quorums for distributed mutual exclusion, This paper a nalyzes the number of messages required to acquire a quorum in TQA. Le t 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 determin e 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 operati onal. Let C-i denote the average number of sites in the quorum that TQ A 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 increa ses. According to the result, an approximate close form for M(i) is de rived.