IEEE/ACM Transactions on Networking · 2007 · 115 citations · 35 references
ComputingComputer ScienceComputer SystemsComputer NetworksDistributed SystemsProbability TheoryNetwork ConnectivityNetwork ReliabilityNetwork ResiliencePeer-to-peer NetworksPeer-to-peer SystemsStochastic NetworksHeavy-tailed DistributionsLifetime DistributionsNetwork LifetimeNode ConnectivityRandom GraphsResilienceResilience In Peer-to-peer NetworksTheoretical Probability
To model P2P networks that are commonly faced with high rates of churn and random departure decisions by end-users, this paper investigates the resilience of random graphs to lifetime-based node failure and derives the expected delay before a user is forcefully isolated from the graph and the probability that this occurs within his/her lifetime. Using these metrics, we show that systems with heavy-tailed lifetime distributions are more resilient than those with light-tailed (e.g., exponential) distributions and that for a given average degree, k-regular graphs exhibit the highest level of fault tolerance. As a practical illustration of our results, each user in a system with n = 100 billion peers, 30-minute average lifetime, and 1-minute node-replacement delay can stay connected to the graph with probability 1 - 1/n using only 9 neighbors. This is in contrast to 37 neighbors required under previous modeling efforts. We finish the paper by observing that many P2P networks are almost surely (i.e., with probability 1 - o(1)) connected if they have no isolated nodes and derive a simple model for the probability that a P2P system partitions under churn.
35
Ion Stoica, Robert Morris, David R. Karger et al. · 2001 · 9.7K citations
A scalable content-addressable network
Sylvia Ratnasamy, Paul Francis, Mark Handley et al. · 2001 · 6.4K citations · Full text
Resilience of the Internet to Random Breakdowns
Reuven Cohen, Keren Erez, Daniel ben‐Avraham et al. · Physical Review Letters · 2000 · 2.4K citations · Full text
Ion Stoica, Robert Morris, David R. Karger et al. · ACM SIGCOMM Computer Communication Review · 2001 · 1.9K citations