2007 · 16 citations · 33 references
ComputingComputer ScienceComputer SystemsComputer NetworksDistributed SystemsQueuing TheoryNetwork ReliabilityNetwork ResilienceNetwork RobustnessNetwork StabilityStochastic NetworksGraph PartitioningHeavy-tailed DistributionsIsolationLifetimesNetwork LifetimeRandom Walk AlgorithmsSelection AlgorithmsUnstructured Peer-to-peer Networks
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.
33
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
A scalable content-addressable network
Sylvia Ratnasamy, Paul Francis, Mark Handley et al. · ACM SIGCOMM Computer Communication Review · 2001 · 1.8K citations