Load Balancing in P2P Networks using Random Walk Algorithm

Previous analytical studies of unstructured P2P resilience have assumed exponential user lifetimes and only considered age-independent neighbor replacement. In this system, the limitations are overcome by introducing a general node-isolation model for heavy-tailed user lifetimes and arbitrary neighbor-selection algorithms. Using this model, analysis of two age-based neighbor-selection strategies takes place and they significantly improve the residual lifetimes of chosen users, which dramatically reduce the probability of user isolation and graph partitioning compared with uniform selection of neighbors. In fact, the second strategy based on random walks on age-proportional graphs demonstrates that, for lifetimes with infinite variance, the system monotonically increases its resilience as its age and size grow. Specifically, it shows the probability of isolation converges to zero as these two metrics tend to infinity. This system is finished with simulations in finite-size graphs that demonstrate the effect of this result in practice.