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.
Abstract
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