Quorum systems constructed from combinatorial designs

A quorum system is a set system in which any two subsets have nonempty inte rsection. Quorum systems have been extensively studied as a method of maint aining consistency in distributed systems, Important attributes of a quorum system include the load, balancing ratio, rank (i,e., quorum size), and av ailability. Many constructions have been presented in the literature for qu orum systems in which these attributes take on optimal or otherwise favorab le values. In this paper, we point out an elementary connection between quo rum systems and the classical covering systems studied in combinatorial des ign theory. We look more closely at the quorum systems that are obtained fr om balanced incomplete block designs (BIBDs). We study the properties of th ese quorum systems and observe that they have load, balancing ratio, and ra nk that are all within a constant factor of being optimal, We also provide several observations about computing the failure polynomials of a quorum sy stem (failure polynomials are used to measure availability). Asymptotic pro perties of failure polynomials have previously been analyzed for certain in finite families of quorum systems. We give an explicit formula for the fail ure polynomials for an easily constructed infinite class of quorum systems. We also develop two algorithms that are useful for computing failure polyn omials for quorum systems and prove that computing failure polynomials is # P-hard. Computational results are presented for several "small" quorum syst ems obtained from BIBDs. (C) 2001 Academic Press.