A quorum system is a collection of sets (quorums) every two
of which intersect. Quorum systems have been used
for many applications in the area of distributed systems,
including mutual exclusion, data replication and
dissemination of information
In this paper we introduce a general class of quorum systems called
Crumbling Walls and study its properties. The elements
(processors) of a wall are logically arranged in rows 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
considerably generalizes a number of known quorum system constructions.
The best crumbling wall is the CWlog quorum system. It has small
quorums, of size O(log n), and structural simplicity.
The CWlog has optimal availability and optimal load
among systems with such small quorum size. It manifests its high
quality for all universe sizes, so it is a good choice
not only for systems with thousands or millions of processors 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.
(Joint work with David Peleg.)