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 Mi be the number of messages required to acquire a quorum or to determine that no quorum is accessible. We discuss Mi as a function of i and p, where p (1/2 < p < 1) is the probability that each site is operational. Let Ci denote the average number of sites in the quorum that TQA finds. The analysis shows that, although both Mi and Ci increase without bound as i increases, Mi/Ciapproaches to 1+p/p as i increases. According to the result, an approximate close form for Mi is derived.