Article

Choosing a random peer

Authors:

Jared SaiaAuthors Info & Claims

PODC '04: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing

Pages 125 - 130

https://doi.org/10.1145/1011767.1011786

Published: 25 July 2004 Publication History

Abstract

We present the first fully distributed algorithm which chooses a peer uniformly at random from the set of all peers in a distributed hash table (DHT). Our algorithm has latency O(log n) and sends O(log n) messages in expectation for a DHT like Chord [17]. Our motivation for studying this problem is threefold: to enable data collection by statistically rigorous sampling methods; to provide support for randomized, distributed algorithms over peer-to-peer networks; and to support the creation and maintenance of random links, and thereby offer a simple means of improving fault-tolerance.

References

[1]

M. Alder, E. Halperin, R. Karp, and V. Vazirani. A stochastic process on the hypercube with applications to peer-to-peer networks. In ACM Symposium on Theory of Computing (STOC), 2003.

Digital Library

[2]

M. Bellare and P. Rogaway. Random oracles are practical: a paradigm for designing efficient protocols. In The First ACM Conference on Computer and Communications Security, pages 62--73, 1993.

Digital Library

[3]

J. Byers, J. Considine, and M. Mitzenmacher. Simple load balancing for distributed hash tables. In Proceedings of the Second Internation Peer to Peer Symposium (IPTPS), 2003.

[4]

C. Gkantsidis, M. Mihail, and A. Saberi. Random walks in peer-to-peer networks. In Conference of the IEEE Communications Society (INFOCOM), 2004.

[5]

D. Karger and M. Ruhl. Finding nearest neighbors in growth-restricted metrics. In ACM Symposium on Theory of Computing (STOC), 2002.

Digital Library

[6]

D. Karger and M. Ruhl. New algorithms for load balancing in peer-to-peer systems. In Proceedings of the Fourth Internation Peer to Peer Symposium (IPTPS), 2004.

[7]

C. Law and K.-Y. Siu. Distributed construction of random expander graphs. In Conference of the IEEE Communications Society (INFOCOM), 2003.

[8]

S. Lewis and J. Saia. Scalable byzantine agreement. Technical report, University of New Mexico, 2004.

[9]

Routing networks for distributed hash tables In ACM Conference on the Principles of Distributed Computing (PODC), 2003.

Digital Library

[10]

D. Malkhi, M. Naor, and D. Ratajczak. Viceroy: A scalable and dynamic emulation of the butterfly network. In ACM Conference on the Principles of Distributed Computing (PODC), 2002.

Digital Library

[11]

R. Motwani and P. Raghavan. Randomized Algorithms, chapter 5.3. Cambridge University Press, 1995.

Digital Library

[12]

R. Motwani and P. Raghavan. Randomized Algorithms, chapter 4. Cambridge University Press, 1995.

Digital Library

[13]

R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.

Digital Library

[14]

M. Naor and U. Weider. Novel architectures for p2p applications: the continuous-discrete approach. In SPAA, 2003.

Digital Library

[15]

S. Saroiu, K. P. Gummadi, R. J. Dunn, S. D. Gribble, and H. M. Levy. An analysis of internet content delivery systems. In Proceedings of the 5th Symposium on Operating Systems Design and Implementation (OSDI), December 2002.

Digital Library

[16]

S. Saroiu, P. K. Gummadi, and S. D. Gribble. A Measurement Study of Peer-to-Peer File Sharing Systems. In Proceedings of Multimedia Computing and Networking, 2002.

[17]

I. Stoica, R. Morris, D. Karger, F. Kaashoek, and H. Balakrishnan. Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications. In Proceedings of the ACM SIGCOMM 2001 Technical Conference, San Diego, CA, USA, August 2001.

Digital Library

Cited By

Khelghatdoust MMahdavi M(2022)A Socially-Aware, Privacy-Preserving, and Scalable Federated Learning Protocol for Distributed Online Social NetworksAdvanced Information Networking and Applications10.1007/978-3-030-99587-4_17(192-203)Online publication date: 31-Mar-2022
https://doi.org/10.1007/978-3-030-99587-4_17
Grall ASkaf-Molli HMolli PPerrin M(2020)Collaborative SPARQL Query Processing for Decentralized Semantic DataDatabase and Expert Systems Applications10.1007/978-3-030-59003-1_21(320-335)Online publication date: 14-Sep-2020
https://doi.org/10.1007/978-3-030-59003-1_21
Aggarwal AFricke GGupta DMoses MRobinson PEllen F(2019)On Site Fidelity and the Price of Ignorance in Swarm Robotic Central Place Foraging AlgorithmsProceedings of the 2019 ACM Symposium on Principles of Distributed Computing10.1145/3293611.3331572(63-65)Online publication date: 16-Jul-2019
https://dl.acm.org/doi/10.1145/3293611.3331572
Show More Cited By

Index Terms

Choosing a random peer
1. Information systems
  1. Information storage systems
    1. Storage architectures
      1. Distributed storage

Recommendations

Choosing a Random Peer in Chord

We present two new algorithms, Arc Length and Peer Count, for choosing a peer uniformly at random from the set of all peers in Chord (Proceedings of the ACM SIGCOMM 2001 Technical Conference, 2001). We show analytically that, in expectation, both ...
Improving lookup latency in distributed hash table systems using random sampling

Distributed hash table (DHT) systems are an important class of peer-to-peer routing infrastructures. They enable scalable wide-area storage and retrieval of information, and will support the rapid development of a wide variety of Internet-scale ...
Locality-Aware and Churn-Resilient Load-Balancing Algorithms in Structured Peer-to-Peer Networks

Structured peer-to-peer overlay networks, like distributed hash tables (DHTs), map data items to the network based on a consistent hashing function. Such mapping for data distribution has an inherent load balance problem. Data redistribution algorithms ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '04: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing

July 2004

422 pages

ISBN:1581138024

DOI:10.1145/1011767

General Chair:
Soma Chaudhuri
Iowa State University
,
Program Chair:
Shay Kutten
Technion

Copyright © 2004 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 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PODC04

Sponsor:

PODC04: Principles of Distributed Computing 2004

July 25 - 28, 2004

Newfoundland, St. John's, Canada

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

81
Total Citations
View Citations
731
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)1

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Khelghatdoust MMahdavi M(2022)A Socially-Aware, Privacy-Preserving, and Scalable Federated Learning Protocol for Distributed Online Social NetworksAdvanced Information Networking and Applications10.1007/978-3-030-99587-4_17(192-203)Online publication date: 31-Mar-2022
https://doi.org/10.1007/978-3-030-99587-4_17
Grall ASkaf-Molli HMolli PPerrin M(2020)Collaborative SPARQL Query Processing for Decentralized Semantic DataDatabase and Expert Systems Applications10.1007/978-3-030-59003-1_21(320-335)Online publication date: 14-Sep-2020
https://doi.org/10.1007/978-3-030-59003-1_21
Aggarwal AFricke GGupta DMoses MRobinson PEllen F(2019)On Site Fidelity and the Price of Ignorance in Swarm Robotic Central Place Foraging AlgorithmsProceedings of the 2019 ACM Symposium on Principles of Distributed Computing10.1145/3293611.3331572(63-65)Online publication date: 16-Jul-2019
https://dl.acm.org/doi/10.1145/3293611.3331572
Gotte TRavindran Vijayalakshmi VScheideler C(2019)Always be Two Steps Ahead of Your Enemy2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS.2019.00114(1073-1082)Online publication date: May-2019
https://doi.org/10.1109/IPDPS.2019.00114
Zhou MZhang RQian WZhou A(2018)Distribution-free data density estimation in large-scale networksFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-016-6194-y12:6(1220-1240)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.1007/s11704-016-6194-y
Felber PKropf PSchiller ESerbu S(2014)Survey on Load Balancing in Peer-to-Peer Distributed Hash TablesIEEE Communications Surveys & Tutorials10.1109/SURV.2013.060313.0015716:1(473-492)Online publication date: Sep-2015
https://doi.org/10.1109/SURV.2013.060313.00157
Guerraoui RHuguenin KKermarrec AMonod MPrusty SRoumy A(2014)Tracking freeriders in gossip-based content dissemination systemsComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2014.02.02364(322-338)Online publication date: 1-May-2014
https://dl.acm.org/doi/10.1016/j.comnet.2014.02.023
Chen HJin HLuo XLiu YGu TChen KNi L(2012)BloomCastIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2011.16823:2(232-241)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1109/TPDS.2011.168
Carzaniga AHall CPapalini M(2012)Fully decentralized estimation of some global properties of a network2012 Proceedings IEEE INFOCOM10.1109/INFCOM.2012.6195806(630-638)Online publication date: Mar-2012
https://doi.org/10.1109/INFCOM.2012.6195806
Zhou MShen HZhou XQian WZhou A(2012)Effective Data Density Estimation in Ring-Based P2P NetworksProceedings of the 2012 IEEE 28th International Conference on Data Engineering10.1109/ICDE.2012.19(594-605)Online publication date: 1-Apr-2012
https://dl.acm.org/doi/10.1109/ICDE.2012.19
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents