Document Type
Conference Paper
Publication Date
5-2007
Publication Source
INFOCOM 2007: 26th IEEE International Conference on Computer Communications
Abstract
Previous analytical studies [12], [18] 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 to uniform selection of neighbors. In fact, the second strategy based on random walks on age-weighted 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
2126 - 2134
ISBN/ISSN
0743-166X
Document Version
Published Version
Copyright
Copyright © 2007 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works.
Publisher
IEEE
Place of Publication
Anchorage, AK
Peer Reviewed
yes
Keywords
graph theory, peer-to-peer computing, probability, age-independent neighbor replacement, age-weighted graph partitioning, infinite variance, node-isolation model, probability, unstructured P2P network, Communications Society, Computational modeling, Computer science, Delay effects, Event detection, H infinity control, Partitioning algorithms, Peer to peer computing, Resilience, USA councils
eCommons Citation
Yao, Zhongmei; Wang, Xiaoming; and Loguinov, Dmitri, "On Node Isolation under Churn in Unstructured P2P Networks with Heavy-Tailed Lifetimes" (2007). Computer Science Faculty Publications. 6.
https://ecommons.udayton.edu/cps_fac_pub/6
Included in
Databases and Information Systems Commons, OS and Networks Commons, Other Computer Sciences Commons, Theory and Algorithms Commons
Comments
Subsequently published in IEEE/ACM Transactions on Networking (Feb. 2009)
Permission documentation is on file.
Publisher Citation
Zhongmei Yao; Xiaoming Wang; Leonard, D.; Loguinov, D., "On Node Isolation Under Churn in Unstructured P2P Networks with Heavy-Tailed Lifetimes," INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE , vol., no., pp.2126,2134, 6-12 May 2007 doi: 10.1109/INFCOM.2007.246