Ittai Abraham

Probabilistic Quorums for Dynamic Systems

Ittai Abraham                  ittaia@cs.huji.ac.il

Dahlia Malkhi                  dalia@cs.huji.ac.il

 

             

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]