CRUMBLING WALLS - A CLASS OF PRACTICAL AND EFFICIENT QUORUM SYSTEMS

A quorum system is a collection of sets (quorums) every two of which i ntersect. Quorum systems have been used for many applications in the a rea of distributed systems, including mutual exclusion, data replicati on and dissemination of information. In this paper we introduce a gene ral class of quorum systems called Crumbling Walls and study its prope rties. The elements (processors) of a wall are logically arranged in r ows of varying widths. A quorum in a wall is the union of one full row and a representative from every row below the full row. This class co nsiderably generalizes a number of known quorum system constructions. The best crumbling wall is the CWlog quorum system. It has small quoru ms, of size O(lg n), and structural simplicity. The CWlog has optimal availability and optimal load among systems with such small quorum siz e. It manifests its high quality for all universe sizes, so it is a go od choice not only for systems with thousands or millions of processor s but also for systems with as few as 3 or 5 processors. Moreover, our analysis shows that the availability will increase and the load will decrease at the optimal rates as the system increases in size.