A symmetric load balancing algorithm with performance guarantees for distributed hash tables

Hung Chang Hsiao, Che Wei Chang

Research output: Contribution to journalArticlepeer-review

26 Citations (Scopus)


Peers participating in a distributed hash table (DHT) may host different numbers of virtual servers and are enabled to balance their loads in the reallocation of virtual servers. Most decentralized load balance algorithms designed for DHTs based on virtual servers require the participating peers to be asymmetric, where some serve as the rendezvous nodes to pair virtual servers and participating peers, thereby introducing another load imbalance problem. While state-of-the-art studies intend to present symmetric load balancing algorithms, they introduce significant algorithmic overheads and guarantee no rigorous performance metrics. In this paper, a novel symmetric load balancing algorithm for DHTs is presented by having the participating peers approximate the system state with histograms and cooperatively implement a global index. Each peer independently reallocates in our proposal its locally hosted virtual servers by publishing and inquiring the global index based on their histograms. Unlike competitive algorithms, our proposal exhibits analytical performance guarantees in terms of the load balance factor and the algorithmic convergence rate, and introduces no load imbalance problem due to the algorithmic workload. Through computer simulations, we show that our proposal clearly outperforms existing distributed algorithms in terms of load balance factor with a comparable movement cost.

Original languageEnglish
Article number6127858
Pages (from-to)662-675
Number of pages14
JournalIEEE Transactions on Computers
Issue number4
Publication statusPublished - 2013

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'A symmetric load balancing algorithm with performance guarantees for distributed hash tables'. Together they form a unique fingerprint.

Cite this