##
Simple Efficient Load Balancing Algorithms for Peer-to-Peer Systems

**
David R. Karger and Matthias Ruhl
**
*
International Workshop on Peer-to-Peer Systems (IPTPS '04)*

San Diego, February 2004

### Abstract

Load balancing is a critical issue for the efficient operation of
peer-to-peer networks. We give two new load-balancing protocols whose
provable performance guarantees are within a constant factor of
optimal. Our protocols refine the *consistent hashing* data
structure that underlies the Chord (and Koorde) P2P network. Both
preserve Chord's logarithmic query time and near-optimal data
migration cost.

Our first protocol balances the distribution of *the key address
space* to nodes, which yields a load-balanced system when the DHT
maps items "randomly" into the address space. To our knowledge, this
yields the first P2P scheme simultaneously achieving O(log *n*)
degree, O(log *n*) look-up cost, and constant-factor load balance
(previous schemes settled for any two of the three).

Our second protocol aims to directly balance the distribution of
*items* among the nodes. This is useful when the distribution of
items in the address space cannot be randomized - for example, if we
wish to support range-searches on "ordered" keys. We give a simple
protocol that balances load by moving nodes to arbitrary locations
"where they are needed." As an application, we use the last protocol
to give an optimal implementation of a distributed data structure for
range searches on ordered data.

Back to publications