Skip to main content
Node Isolation Model and Age-Based Neighbor Selection in Unstructured P2P Networks
IEEE/ACM Transactions on Networking
  • Zhongmei Yao, University of Dayton
  • Derek Leonard, Texas A & M University - College Station
  • Dmitri Loguinov, Texas A & M University - College Station
Document Type
Publication Date

Previous analytical studies of unstructured P2P resilience have assumed exponential user lifetimes and only considered age-independent neighbor replacement. In this paper, we overcome these limitations by introducing a general node-isolation model for heavy-tailed user lifetimes and arbitrary neighbor-selection algorithms. Using this model, we analyze two age-biased neighbor-selection strategies and show that they significantly improve the residual lifetimes of chosen users, which dramatically reduces 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, we show that the probability of isolation converges to zero as these two metrics tend to infinity. We finish the paper with simulations in finite-size graphs that demonstrate the effect of this result in practice.

Inclusive pages
144 - 157
Document Version

Permission documentation is on file.

Publisher Citation
Zhongmei Yao; Xiaoming Wang; Leonard, D.; Loguinov, D., "Node Isolation Model and Age-Based Neighbor Selection in Unstructured P2P Networks," Networking, IEEE/ACM Transactions on , vol.17, no.1, pp.144,157, Feb. 2009 doi: 10.1109/TNET.2008.925626

Peer Reviewed
  • graph theory,
  • peer-to-peer computing,
  • probability,
  • random processes,
  • telecommunication network reliability,
  • age-proportional graphs,
  • arbitrary age-biased neighbor-selection algorithm,
  • exponential user lifetimes,
  • finite-size graphs,
  • graph partitioning,
  • heavy-tailed user lifetimes,
  • node-isolation model,
  • probability,
  • random walks,
  • residual lifetimes,
  • unstructured P2P network resilience,
  • user isolation,
  • Age-based selection,
  • heavy-tailed lifetimes,
  • node isolation,
  • peer-to-peer networks,
  • user churn
Citation Information
Zhongmei Yao, Derek Leonard and Dmitri Loguinov. "Node Isolation Model and Age-Based Neighbor Selection in Unstructured P2P Networks" IEEE/ACM Transactions on Networking Vol. 17 Iss. 1 (2009)
Available at: