Randomized load balancing strategies with churn resilience in peer-to-peer networks

The objective of load balancing in peer-to-peer (P2P) networks is to balance the workload of peer nodes in proportion to their capacity so as to eliminate performance bottlenecks. It is challenging because of the dynamic nature in overlay networks, the time-varying load characteristics, and the inherent load imbalance caused by consistent hashing functions. It is known that simple randomized load balancing schemes can balance load effectively while incurring only a small overhead in general parallel and distributed computing contexts. Existing theoretical works which analyze properties of randomized load balancing schemes cannot be applied in the highly dynamic and heterogeneous P2P systems. In this paper, we characterize the behaviors of randomized load balancing schemes in a general P2P environment. We extend the supermarket model by investigating the impact of node heterogeneity and chum on load distribution in P2P networks. We prove that by using d-way random choices schemes, the length of the longest queue in a P2P system with heterogeneous nodes and chum for d >= 2 is c * log logn/logd + O(1) with high probability, where c is a constant. Our results have wide applicability and are of interest beyond the specific applications. (C) 2010 Elsevier Ltd. All rights reserved.