Accessing probabilistic quorums in dynamic networks
WRAS '10: Proceedings of the Third International Workshop on Reliability, Availability, and Security
Article No.: 3, Pages 1 - 6
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 [12]. Unfortunately, most existent analytic results for accessing probabilistic quorums are tailored to static networks [8]. 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 round. We show that O(n3 log n) communication steps are needed to access a probabilistic quorum under these conditions.
References
[1]
Ittai Abraham and Dahlia Malkhi. Probabilistic quorums for dynamic systems. Distrib. Comput., 18(2):113--124, 2005.
[2]
David Aldous and James Allen Fill. Reversible Markov Chains and Random Walks on Graphs. unpublished, 1995.
[3]
Romas Aleliunas, Richard M. Karp, Richard J. Lipton, László Lovász, and Charles Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. In FOCS '79: 20th Annual Symposium on Foundations of Computer Science, pages 218--223, 1979.
[4]
Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. Sharing memory robustly in message-passing systems. J. ACM, 42(1):124--142, 1995.
[5]
Chen Avin, Michal Koucký, and Zvi Lotker. How to explore a fast-changing world (cover time of a simple random walk on evolving graphs). In ICALP '08: Proceedings of the 35th international colloquium on Automata, Languages and Programming, Part I, pages 121--132, Berlin, Heidelberg, 2008. Springer-Verlag.
[6]
Ziv Bar-Yossef, Roy Friedman, and Gabriel Kliot. Rawms - random walk based lightweight membership service for wireless ad hoc networks. ACM Trans. Comput. Syst., 26(2):1--66, 2008.
[7]
Roy Friedman and Gabriel Kliot. Location services in wireless ad hoc and hybrid networks: A survey. Technical report, Technion Computer Science, 2006.
[8]
Roy Friedman, Gabriel Kliot, and Chen Avin. Probabilistic quorum systems in wireless ad hoc networks. In In Proceedings of the 38th IEEE International Conference on Dependable Systems and Networks (DSN-DCCS), 2008.
[9]
Rachid Guerraoui and Michel Raynal. The information structure of indulgent consensus. IEEE Trans. Comput., 53(4):453--466, 2004.
[10]
Fabian Kuhn, Nancy Lynch, and Rotem Oshman. Distributed computation in dynamic networks. In STOC '10: Proceedings of the 42nd ACM Symposium on Theory of Computing, page to appear, Cambridge, Massachusetts, USA, 2010. ACM.
[11]
Jun Luo, Jean-Pierre Hubaux, and Patrick Th. Eugster. Pan: providing reliable storage in mobile ad hoc networks with probabilistic quorum systems. In MobiHoc '03: Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, pages 1--12, New York, NY, USA, 2003. ACM.
[12]
Dahlia Malkhi, Michael Reiter, and Rebecca Wright. Probabilistic quorum systems. In PODC '97: Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, pages 267--273, New York, NY, USA, 1997. ACM.
[13]
Ken Miura, Taro Tagawa, and Hirotsugu Kakugawa. A quorum-based protocol for searching objects in peer-to-peer networks. IEEE Trans. Parallel Distrib. Syst., 17(1):25--37, 2006.
[14]
Ravi Montenegro. The simple random walk and max-degree walk on a directed graph. Random Struct. Algorithms, 34(3):395--407, 2009.
Index Terms
- Accessing probabilistic quorums in dynamic networks
Recommendations
Probabilistic quorums for dynamic systems
Special issue: DISC 03A quorum system is a set of sets such that every two sets in the quorum system intersect. Quorum systems are well known building blocks for maintaining information in a distributed system while providing high availability and good load balance. ...
Are quorums an alternative for data replication?
Data replication is playing an increasingly important role in the design of parallel information systems. In particular, the widespread use of cluster architectures often requires to replicate data for performance and availability reasons. However, ...
Timed quorum systems for large-scale and dynamic environments
OPODIS'07: Proceedings of the 11th international conference on Principles of distributed systemsThis paper presents Timed Quorum System (TQS), a quorum system for large-scale and dynamic systems. TQS provides guarantees that two quorums, accessed at instances of time that are close together, intersect with high probability. We present an algorithm ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2010
62 pages
Copyright © 2010 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 25 July 2010
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Conference
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 68Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 25 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in