Probabilistic
Quorums for Dynamic Systems
Abstract
A quorum system is a set of sets such that
every two sets in the quorum system intersect. Quorum systems may be used as a building
block for performing updates and global queries on a distributed, shared
information base. An $\varepsilon$-intersecting
quorum system is a distribution on sets such that every two sets from the distribution
intersect with probability $1-\varepsilon$. This relaxation of consistency
results in a dramatic improvement of the load balancing and resilience of
quorum systems, making the approach especially attractive for scalable and
dynamic settings.
In this paper we assume a dynamic model where
nodes constantly join and leave the system. A quorum chosen at time $s$ must
evolve and transform as the system grows/shrinks in order to remain viable. For
such a dynamic model, we introduce dynamic $\varepsilon$-intersecting
quorum systems. A dynamic $\varepsilon$-intersecting
quorum system ensures that in spite of arbitrary changes in the system
population, any two evolved quorums intersect with probability $1-\varepsilon$.
(Best Student Paper Award)
[TR version pdf]
[DISC version pdf]