Minimizing the mean delay of quorum-based mutual exclusion schemes

Achieving mutual exclusion is one of the most fundamental problems in distr ibuted computing. The use of coteries is a well-known approach to this prob lem. A coterie is a special set of pair-wise intersecting node groups calle d quorums. The communication delay incurred in a quorum-based mutual exclus ion scheme depends critically on the coterie adopted, and thus it is import ant to find a coterie with small delay. Recently, two related measures call ed max-delay and mean-delay have been introduced. The former measure repres ents the largest delay among all nodes, while the latter is the arithmetic mean of the delays. In a previous paper, we have proposed a polynomial-time algorithm to find max-delay optimal coteries, but there has been no algori thm to find mean-delay optimal coteries. In this paper, the first algorithm that finds mean-delay optimal coteries in general topology networks is pro posed. This algorithm employs the branch-and-bound method to effectively ex plore the search space. Although its running time can be exponential, it is shown that the algorithm is applicable to moderate-sized networks through experiments. (C) 2001 Elsevier Science Inc. All rights reserved.