Distributed Tries for Load Balancing in Peer-to-Peer Systems

Free registration required

Executive Summary

In structured peer-to-peer (p2p) systems, Distributed Hash Tables (DHTs) often partition the ID space into disjoint intervals with each interval assigned to the corresponding node. While nodes join and leave dynamically, one of the hard challenges posed by DHTs is load balancing across the ID space. Tries are known to be a viable data structure such that a balanced trie implies balanced intervals in the ID space. The authors establish a distributed trie as a deployable overlay network that connects the IDs of participating nodes. They propose a decentralized, efficient, and low-cost algorithm that balances ID intervals in DHTs using the trie.

  • Format: PDF
  • Size: 186.73 KB