skip to main content
10.1145/1073970.1074008acmconferencesArticle/Chapter ViewAbstractPublication PagesspaaConference Proceedingsconference-collections
Article

Weighted distributed hash tables

Published:18 July 2005Publication History

ABSTRACT

We present two methods for weighted consistent hashing also known as weighted distributed hash tables. The first method, called Linear Method, combines the standard consistent hasing introduced by Karger et al. [9] with a linear weighted distance measure. By using node copies and different partitions of the hash space, the balance of this scheme approximates the fair weight relationship with high probability. The second method, called the Logarithmic Method, uses a logarithmic weighted distance between the peers and the data to find the corresponding node. For distributing one data element it provides perfect weighted balance. To provide this distribution for many data elements we use partitions to achieve a fair balance with high probability. These methods provide small fragmentation, which means that the hash space is divided into at most O (n log n) intervals. Furthermore, there is an efficient data structure that assigns data elements to the nodes in expected time O (log n). If small fragmentation is not an issue one can replace the use of partitions by a method we call double hash functions. This method needs O (n) for assigning elements to a node, yet it can be directly used for Storage Area Networks, where the number of nodes is small compared to participating nodes in Peer-to-Peer networks.

References

  1. P. K. Agarwal and M. Sharir. Simple bounds. In Davenport-Schinzel Sequences and Their Geometric Applications, chapter 1, pages 1--47. Cambridge University Press, in handbook of computational geometry edition, 1995. ISBN 0-521-47025-0.Google ScholarGoogle Scholar
  2. P. Bleckmann, S. Böttcher, E. Cesnavicius, A. Francisco, T. D. Hollerung, B. Kühnel, M. J. Liu, S. Obermeier, S. Oberthür, F. Peter, F. Rammig, C. Schindelhauer, G. Schomaker, T. Steenweg, Q. A. Tarar, M. Tiemeyer, A. Türling, and A. Vater. The design of pamanet the paderborn mobile ad-hoc network. In MobiWac '04: Proceedings of the second international workshop on Mobility management & wireless access protocols, pages 119--121, New York, NY, USA, 2004. ACM Press. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. A. Brinkmann, F. Meyer auf der Heide, K. Salzwedel, C. Scheideler, M. Vodisek, and U. Rückert. Storage management as means to cope with exponential information growth. In Proceedings of SSGRR 2003, L'Aquila, Italy, 28 July - 3 Aug. 2003.Google ScholarGoogle Scholar
  4. A. Brinkmann, K. Salzwedel, and C. Scheideler. Efficient, distributed data placement strategies for storage area networks (extended abstract). In Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, pages 119--128. ACM Press, 2000. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. A. Brinkmann, K. Salzwedel, and C. Scheideler. Compact, adaptive placement schemes for non-uniform distribution requirements. In Proc. of the 14th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 53--62, Winnipeg, Manitoba, Canada, 11-13 Aug. 2002. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. J. Byers, J. Considine, and M. Mitzenmacher. Simple load balancing for distributed hash tables. Technical report, BU Computer Science, 2002.Google ScholarGoogle Scholar
  7. P. Druschel and A. Rowstron. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In R. Guerraoui, editor, Middleware 2001, IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, Germany, November 12-16, 2001, Proceedings, volume 2218 of Lecture Notes in Computer Science, pages 329--350. Springer, 2001. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. K. Hildrum, J. D. Kubiatowicz, S. Rao, and B. Y. Zhao. Distributed object location in a dynamic network. In Proceedings of the 14th Annual ACM Symposium on Parallel ALgorithms and Architectures (SPAA-02), pages 41--52, New York, Aug. 10--13 2002. ACM Press. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. D. Karger, E. Lehman, T. Leighton, M. Levine, D. Lewin, and R. Panigrahy. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 654--663, El Paso, Texas, 4--6 May 1997. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. D. R. Karger and M. F. Kaashoek. Koorde: A simple degree-optimal distributed hash table. In Proc. 2nd IPTPS, Berkeley, CA, Feb. 2003, Feb. 10 2003.Google ScholarGoogle Scholar
  11. M. Mitzenmacher. The power of two choices in randomized load balancing. IEEE Transactions on Parallel and Distributed Systems, 12(10):1094--1104, 2001. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. M. Naor and U. Wieder. Novel architectures for p2p applications: the continuous-discrete approach. In Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, pages 50--59. ACM Press, 2003. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. C. G. Plaxton, R. Rajaraman, and A. Richa. Accessing nearby copies of replicated objects in a distributed environment. In 9th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '97), pages 311--320, New York, June 1997. Association for Computing Machinery. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. A. Rao, K. Lakshminarayanan, S. Surana, R. Karp, and I. Stoica. Load balancing in structured p2p systems. In 2nd International Workshop on Peer-to-Peer Systems (IPTPS '03), 2003.Google ScholarGoogle ScholarCross RefCross Ref
  15. S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker. A scalable content-addressable network. In Computer Communication Review, volume 31, pages 161--172. Dept. of Elec. Eng. and Comp. Sci., University of California, Berkeley, 2001. Google ScholarGoogle ScholarDigital LibraryDigital Library
  16. I. Stoica, R. Morris, D. Karger, F. Kaashoek, and H. Balakrishnan. Chord: A scalable Peer-To-Peer lookup service for internet applications. In R. Guerin, editor, Proceedings of the ACM SIGCOMM 2001Conference (SIGCOMM-01), volume 31, 4 of Computer Communication Review, pages 149--160, New York, Aug. 27--31 2001. ACM Press. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. B. Zhao, J. Kubiatowicz, and A. Joseph. Tapestry: An infrastructure for fault-tolerant wide-area location and routing. Technical Report UCB/CSD-01-1141, Computer Science Division, U. C. Berkeley, Apr. 2001. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Weighted distributed hash tables

                Recommendations

                Comments

                Login options

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

                Sign in
                • Published in

                  cover image ACM Conferences
                  SPAA '05: Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures
                  July 2005
                  346 pages
                  ISBN:1581139861
                  DOI:10.1145/1073970
                  • General Chair:
                  • Phil Gibbons,
                  • Program Chair:
                  • Paul Spirakis

                  Copyright © 2005 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]

                  Publisher

                  Association for Computing Machinery

                  New York, NY, United States

                  Publication History

                  • Published: 18 July 2005

                  Permissions

                  Request permissions about this article.

                  Request Permissions

                  Check for updates

                  Qualifiers

                  • Article

                  Acceptance Rates

                  Overall Acceptance Rate447of1,461submissions,31%

                  Upcoming Conference

                  SPAA '24

                PDF Format

                View or Download as a PDF file.

                PDF

                eReader

                View online with eReader.

                eReader