Document Type

Article

Publication Date

12-2008

Publication Source

IEEE/ACM Transactions on Networking

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.

ISBN/ISSN

1063-6692

Document Version

Postprint

Comments

This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in IEEE/ACM Transactions on Networking, Vol. 16, Issue 6 (2008).

Some differences may exist between the manuscript and the published version; as such, researchers wishing to quote directly from this resource are advised to consult the version of record.

Permission documentation is on file.

Publisher

IEEE

Volume

16

Peer Reviewed

yes

Issue

6

Keywords

P2P networks, node failure, network disconnection

Download
Link to published version

Share

COinS