Accessing Probabilistic Quorums in Dynamic Networks.

O. Denysyuk and L. Rodrigues

Selected sections of this report were published in the proceedings of the 3rd ACM SIGOPS/SIGACT Workshop on Reliability, Availability, and Security, Zurich, Switzerland, July 2010.


Quorums are a fundamental building block for solving various fundamental problems such as consensus, distributed dictionaries, distributed storage, among others. In particular, probabilistic quorums have shown to be scalable, efficient, and suitable for dynamic environments. Unfortunately, most existent analytic results for accessing probabilistic quorums are tailored to static networks. However, we believe that the correct functioning of such systems must be assured in a much wider range of scenarios.

In this paper, we discuss the random walk based scheme for accessing probabilistic quorums in dynamic networks where an oblivious adversary changes the communication links arbitrarily in each communication step. We show that kO(n^3 ln(n)) communication steps are needed to access a probabilistic quorum under these conditions.

Also available extended report (pdf)

Luís Rodrigues