THE AVAILABILITY OF CRUMBLING WALL QUORUM SYSTEMS

A quorum is system is a collection of sets (quorums) every two of whic h intersect. Quorum systems have been used for many applications in th e area of distributed systems, including mutual exclusion, data replic ation and dissemination of information. Crumbling walls are a general class of quorum systems. The elements (processors) of a wall are logic ally arranged in rows of varying widths. A quorum in a wall is the uni on of one full row and a representative from every row below the full row. This class considerably generalizes a number of known quorum syst em constructions. In this paper we study the availability of crumbling wall quorum systems. We show that if the row width is bounded, or if the number of rows is bounded, then the wall's failure probability F-p does not vanish as the number of elements tends to infinity (i.e., F- p is not Condorcet). If the wall may grow in both the row number and r ow width, we show that the behavior depends on the rate of growth of t he row width. We establish a sharp threshold rate: when the row width n(i) less than or equal to [log(2)i] then F-p is Condorcet, and when n (i) greater than or equal to (1 + epsilon) log(2) i then F-p is not Co ndorcet.