Article

Routing networks for distributed hash tables

Author:

Gurmeet Singh MankuAuthors Info & Claims

PODC '03: Proceedings of the twenty-second annual symposium on Principles of distributed computing

Pages 133 - 142

https://doi.org/10.1145/872035.872054

Published: 13 July 2003 Publication History

Abstract

Routing topologies for distributed hashing in peer-to-peer networks are classified into two categories: deterministic and randomized. A general technique for constructing deterministic routing topologies is presented. Using this technique, classical parallel interconnection networks can be adapted to handle the dynamic nature of participants in peer-to-peer networks. A unified picture of randomized routing topologies is also presented. Two new protocols are described which improve average latency as a function of out-degree. One of the protocols can be shown to be optimal with high probability. Finally, routing networks for distributed hashing are revisited from a systems perspective and several open design problems are listed.

References

[1]

I. Abraham, B. Awerbuch, Y. Azar, Y. Bartal, D. Malkhi, and E. Pavlov. A generic scheme for building overlay networks in adversarial scenarios. In Proc. Intl. Parallel and Distributed Processing Symp., Apr 2003.

Digital Library

[2]

M. Adler, E. Halperin, R. M. Karp, and V. V. Vazirani. A stochastic process on the hypercube with applications to peer-to-peer networks. In Proc. 35nd ACM Symp. on Theory of Computing (STOC 2003), Jun 2003.

Digital Library

[3]

J. Aspnes, Z. Diamadi, and G. Shah. Fault-tolerant routing in peer-to-peer systems. In Proc. 21st ACM Symp. on Principles of Distributed Computing (PODC 2002), pages 223--232, Jul 2002.

Digital Library

[4]

L. Barriere, P. Fraigniaud, E. Kranakis, and D. Krizanc. Efficient routing in networks with long range contacts. In Proc. 15th Intl. Symp. on Distributed Computing (DISC 01), pages 270--284, 2001.

Digital Library

[5]

B. Bollobas. Random Graphs. Cambridge University Press, 2nd edition, 2001.

[6]

M. Castro, P. Druschel, Y. C. Hu, and A. Rowstron. Topology-aware routing in structured peer-to-peer overlay networks. In Proc. Intl. Workshop on Future Directions in Distrib. Computing (FuDiCo 2002), 2002.

Digital Library

[7]

J. Considine and T. Florio. Scalable peer-to-peer indexing with constant state. Technical Report 2002-026, Computer Science Deptt., Boston University, Sep 2002.

[8]

J. Duato, S. Yalamanchili, and L. Ni. Interconnection Networks: An Engineering Approach. IEEE Press, 1997.

Digital Library

[9]

P. Flajolet and G. N. Martin. Probabilistic counting. In Proc. 24th Annual Symp. on Foundations of Computer Science (FOCS 1983), pages 76--82, 1983.

Digital Library

[10]

P. Fraigniaud and C. Gavoille. The content-addressable network d2b. Technical Report 1349, LRI, Univ. Paris-Sud, France, Jan 2003.

[11]

P. Gibbons. Distinct sampling for highly-accurate answers to distinct value queries and event reports. In Proc. 27th Intl. Conf. on Very Large Data Bases (VLDB 2001), pages 541--550, 2001.

Digital Library

[12]

S. D. Gribble, E. A. Brewer, J. M. Hellerstein, and D. Culler. Scalable, distributed data structures for internet service construction. In Proc. 4th Symposium on Operating System Design and Implementation (OSDI 2000), pages 319--332, 2000.

Digital Library

[13]

K. Hildrum, J. D. Kubiatowicz, S. Rao, and B. Y. Zhao. Distributed object location in a dynamic network. In Proc. 14th ACM Symposium on Parallel Algorithms and Architectures (SPAA 2002), pages 41--52, 2002.

Digital Library

[14]

F. Kaashoek and D. R. Karger. Koorde: A simple degree-optimal hash table. In Proc. 2nd Intl. Workshop on Peer-to-Peer Systems (IPTPS 2003), 2003.

[15]

J. Kleinberg. The small-world phenomenon: An algorithmic perspective. In Proc. 32nd ACM Symposium on Theory of Computing (STOC 2000), pages 163--170, 2000.

Digital Library

[16]

L. G. Valiant. A scheme for fast parallel communication. SIAM J. of Computing, 11:350--361, 1982.

[17]

F. T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays - Trees - Hypercubes. Morgan Kanfmann, 1992.

Digital Library

[18]

W. Litwin, M. Neimat, and D. A. Schneider. LH* - A scalable, distributed data structure. ACM Transactions On Database Systems, 21(4):480--525, 1996.

Digital Library

[19]

D. Malkhi, M. Naor, and D. Ratajczak. Viceroy: A scalable and dynamic emulation of the butterfly. In Proc 21st ACM Symposium on Principles of Distributed Computing (PODC 2002), pages 183--192, 2002.

Digital Library

[20]

G. S. Manku, M. Bawa, and P. Raghavan. Symphony: Distributed hashing in a small world. Proc. 4th USENIX Symposium on Internet Technologies and Systems (USITS 2003), 2003.

Digital Library

[21]

S. Milgram. The small world problem. Psychology Today, 67(1), 1967.

[22]

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

Digital Library

[23]

N. de Bruijn. A combinatorial problem. Proc. Kominklitjke Nederlandse Akademie van Wetenschappen, 49:758--764, 1946.

[24]

M. Naor and U. Wieder. Novel architectures for p2p applications: The continuous-discrete approach. In Proc. 15th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA-2003), Jun 2003.

Digital Library

[25]

C. G. Plaxton, R. Rajaraman, and A. W. Richa. Accessing nearby copies of replicated objects in a distributed environment. In Proc. 9th ACM Symposium on Parallel Algorithms and Architectures (SPAA 1997), pages 311--320, 1997.

Digital Library

[26]

S. Ratnasamy, P. Francis, M. Handley, and R. M. Karp. A scalable content-addressable network. In Proc. ACM SIGCOMM 2001, pages 161--172, 2001.

Digital Library

[27]

S. Ratnasamy, M. Handley, R. M. Karp, and S. Shenker. Topologically-aware overlay construction and server selection. In Proc. IEEE INFOCOM-2002, Jun 2002.

[28]

A. I. T. Rowstron and P. Druschel. Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. In IFIP/ACM International Conference on Distributed Systems Platforms (Middleware 2001), pages 329--350, 2001.

Digital Library

[29]

I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In Proc. ACM SIGCOMM 2001, pages 149--160, 2001.

Digital Library

Cited By

Balatsouras CKarras AKarras CTsolis DSioutas S(2022)WiCHORD: A Chord Protocol Application on P2P LoRa Wireless Sensor Networks2022 13th International Conference on Information, Intelligence, Systems & Applications (IISA)10.1109/IISA56318.2022.9904339(1-8)Online publication date: 18-Jul-2022
https://doi.org/10.1109/IISA56318.2022.9904339
Cheng LLi T(2016)Efficient Data Redistribution to Speedup Big Data Analytics in Large Systems2016 IEEE 23rd International Conference on High Performance Computing (HiPC)10.1109/HiPC.2016.020(91-100)Online publication date: Dec-2016
https://doi.org/10.1109/HiPC.2016.020
Jesus PBaquero CAlmeida P(2015)A Survey of Distributed Data Aggregation AlgorithmsIEEE Communications Surveys & Tutorials10.1109/COMST.2014.235439817:1(381-404)Online publication date: Sep-2016
https://doi.org/10.1109/COMST.2014.2354398
Show More Cited By

Index Terms

Routing networks for distributed hash tables

Recommendations

On Routing in Distributed Hash Tables
P2P '07: Proceedings of the Seventh IEEE International Conference on Peer-to-Peer Computing

There have been many proposals for constructing routing tables for Distributed Hash Tables (DHT). They can be classified into two groups: A) those that assume that the peers are uniformly randomly distributed in the identifier space, and B) those that ...
Scalable blind search and broadcasting over Distributed Hash Tables

Typical blind search algorithms in P2P networks generate a significant amount of duplicate query messages in order to increase the success rate. We present a novel framework, named Recursive Partitioning Search (RPS), for blind search over structured ...
Replica Placement for Route Diversity in Tree-Based Routing Distributed Hash Tables

Distributed hash tables (DHTs) share storage and routing responsibility among all nodes in a peer-to-peer network. These networks have bounded path length unlike unstructured networks. Unfortunately, nodes can deny access to keys or misroute lookups. We ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '03: Proceedings of the twenty-second annual symposium on Principles of distributed computing

July 2003

380 pages

ISBN:1581137087

DOI:10.1145/872035

General Chair:
Elizabeth Borowsky
Boston Coll.
,
Program Chair:
Sergio Rajsbaum
UNAM

Copyright © 2003 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: 13 July 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PODC03

Sponsor:

PODC03: Twenty-Second Annual ACM Symposium on Principles of Distributed Computing

July 13 - 16, 2003

Massachusetts, Boston

Acceptance Rates

PODC '03 Paper Acceptance Rate 51 of 226 submissions, 23%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

65
Total Citations
View Citations
1,495
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)2

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Balatsouras CKarras AKarras CTsolis DSioutas S(2022)WiCHORD: A Chord Protocol Application on P2P LoRa Wireless Sensor Networks2022 13th International Conference on Information, Intelligence, Systems & Applications (IISA)10.1109/IISA56318.2022.9904339(1-8)Online publication date: 18-Jul-2022
https://doi.org/10.1109/IISA56318.2022.9904339
Cheng LLi T(2016)Efficient Data Redistribution to Speedup Big Data Analytics in Large Systems2016 IEEE 23rd International Conference on High Performance Computing (HiPC)10.1109/HiPC.2016.020(91-100)Online publication date: Dec-2016
https://doi.org/10.1109/HiPC.2016.020
Jesus PBaquero CAlmeida P(2015)A Survey of Distributed Data Aggregation AlgorithmsIEEE Communications Surveys & Tutorials10.1109/COMST.2014.235439817:1(381-404)Online publication date: Sep-2016
https://doi.org/10.1109/COMST.2014.2354398
Cheng LKotoulas SWard TTheodoropoulos G(2013)QbDJ: A Novel Framework for Handling Skew in Parallel Join Processing on Distributed Memory2013 IEEE 10th International Conference on High Performance Computing and Communications & 2013 IEEE International Conference on Embedded and Ubiquitous Computing10.1109/HPCC.and.EUC.2013.214(1519-1527)Online publication date: Nov-2013
https://doi.org/10.1109/HPCC.and.EUC.2013.214
Ji SHe JCai Z(2013)Data Gathering in Wireless Sensor NetworksThe Art of Wireless Sensor Networks10.1007/978-3-642-40009-4_16(535-565)Online publication date: 14-Dec-2013
https://doi.org/10.1007/978-3-642-40009-4_16
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
Zhang YLiu L(2012)Distributed Line GraphsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2011.25824:9(1556-1569)Online publication date: 1-Sep-2012
https://dl.acm.org/doi/10.1109/TKDE.2011.258
Varagnolo DPillonetto GSchenato L(2012)Consensus based estimation of anonymous networks size using Bernoulli trials2012 American Control Conference (ACC)10.1109/ACC.2012.6314621(2196-2201)Online publication date: Jun-2012
https://doi.org/10.1109/ACC.2012.6314621
Jacobs TPandurangan G(2012)Stochastic analysis of a churn-tolerant structured peer-to-peer schemePeer-to-Peer Networking and Applications10.1007/s12083-012-0124-z6:1(1-14)Online publication date: 3-Feb-2012
https://doi.org/10.1007/s12083-012-0124-z
Apolónia NFerreira PVeiga L(2012)Enhancing Online Communities with Cycle-Sharing for Social NetworksComputational Social Networks10.1007/978-1-4471-4048-1_7(161-195)Online publication date: 19-May-2012
https://doi.org/10.1007/978-1-4471-4048-1_7
Show More Cited By

View Options

Get Access

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