  This paper studies the problem of load-balancing the demand for content in a
peer-to-peer network across heterogeneous peer nodes that hold replicas of the
content. Previous decentralized load balancing techniques in distributed
systems base their decisions on periodic updates containing information about
load or available capacity observed at the serving entities. We show that these
techniques do not work well in the peer-to-peer context; either they do not
address peer node heterogeneity, or they suffer from significant load
oscillations. We propose a new decentralized algorithm, Max-Cap, based on the
maximum inherent capacities of the replica nodes and show that unlike previous
algorithms, it is not tied to the timeliness or frequency of updates. Yet,
Max-Cap can handle the heterogeneity of a peer-to-peer environment without
suffering from load oscillations.
