Document Type
Conference Paper
Publication Date
11-2005
Publication Source
Proceedings of the 13th IEEE International Conference on Network Protocols
Abstract
In this paper, we analyze the problem of network disconnection in the context of large-scale P2P networks and understand how both static and dynamic patterns of node failure affect the resilience of such graphs. We start by applying classical results from random graph theory to show that a large variety of deterministic and random P2P graphs almost surely (i.e., with probability 1-o(1)) remain connected under random failure if and only if they have no isolated nodes. This simple, yet powerful, result subsequently allows us to derive in closed-form the probability that a P2P network develops isolated nodes, and therefore partitions, under both types of node failure. We finish the paper by demonstrating that our models match simulations very well and that dynamic P2P systems are extremely resilient under node churn as long as the neighbor replacement delay is much smaller than the average user lifetime.
Inclusive pages
344-357
ISBN/ISSN
0-7695-2437-0
Document Version
Published Version
Copyright
Copyright © 2005 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
Boston, MA
Peer Reviewed
yes
Keywords
graph theory, large-scale systems, peer-to-peer computing, probability, random processes, P2P network, average user lifetime, deterministic graph, dynamic partitioning behavior, large-scale network, probability, random graph theory, static partitioning behavior, Computer science, Delay, Explosions, Failure analysis, Graph theory, Large-scale systems, Pattern analysis, Performance analysis, Power system modeling, Resilience
eCommons Citation
Leonard, Derek; Yao, Zhongmei; Wang, Xiaoming; and Loguinov, Dmitri, "On Static and Dynamic Partitioning Behavior of Large-Scale Networks" (2005). Computer Science Faculty Publications. 1.
https://ecommons.udayton.edu/cps_fac_pub/1
Included in
Databases and Information Systems Commons, Information Security Commons, OS and Networks Commons, Other Computer Sciences Commons, Theory and Algorithms Commons
Comments
Subsequently published in IEEE/ACM Transactions on Networking, Vol. 16, No. 6 (December 2008).
Permission documentation is on file.
Publisher Citation
Leonard, D.; Zhongmei Yao; Xiaoming Wang; Loguinov, D., "On static and dynamic partitioning behavior of large-scale networks," Network Protocols, 2005. ICNP 2005. 13th IEEE International Conference on , vol., no., pp.13 pp.,357, 9-9 Nov. 2005 doi: 10.1109/ICNP.2005.27