What does it take to disconnect a P2P network?
Conference Paper
Overview
Identity
Additional Document Info
View All
Overview
abstract
We analyze the problem of network disconnection in the context of large-scale P2P net- works and attempt to 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 al- most 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 with examples that demonstrate 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.
