Heterogeneity and load balance in distributed hash tables

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Existing solutions to balance load in DHTs incur a high overhead either in terms of routing state or in terms of load movement generated by nodes arriving or departing the system. In this paper, we propose a set of general techniques and use them to develop a protocol based on Chord, called Y 0, that achieves load balancing with minimal overhead under the typical assumption that the load is uniformly distributed in the identifier space. In particular, we prove that Y 0 can achieve near-optimal load balancing, while moving little load to maintain the balance and increasing the size of the routing tables by at most a constant factor. Using extensive simulations based on real-world and synthetic capacity distributions, we show that Y 0 reduces the load imbalance of Chord from O(log n) to a less than 3.6 without increasing the number of links that a node needs to maintain. In addition, we study the effect of heterogeneity on both DHTs, demonstrating significantly reduced average route length as node capacities become increasingly heterogeneous. For a real-word distribution of node capacities, the route length in Y 0 is asymptotically less than half the route length in the case of a homogeneous system.

Original languageEnglish (US)
Title of host publicationProceedings - IEEE INFOCOM 2005. The Conference on Computer Communications - 24th Annual Joint Conference of the IEEE Computer and Communications Societies
EditorsK. Makki, E. Knightly
Number of pages11
StatePublished - 2005
Externally publishedYes
EventIEEE INFOCOM 2005 - Miami, FL, United States
Duration: Mar 13 2005Mar 17 2005

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


Country/TerritoryUnited States
CityMiami, FL

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering


Dive into the research topics of 'Heterogeneity and load balance in distributed hash tables'. Together they form a unique fingerprint.

Cite this