skip to main content
article

On static and dynamic partitioning behavior of large-scale P2P networks

Published: 01 December 2008 Publication History

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.

References

[1]
D. J. Aldous and M. Brown, "Inequalities for rare events in time-reversible markov chains II," Stochastic Processes Appl., vol. 44, pp. 15-25, 1993.
[2]
R. Arratia, L. Goldstein, and L. Gordon, "Two moments suffice for poisson approximations: The Chen-Stein method," The Annals of Probability , vol. 17, no. 1, pp. 9-25, Jan. 1989.
[3]
S. N. Bernstein, "Sur Les Fonctions Absolument Monotones," Acta Math., vol. 52, pp. 1-66, 1928.
[4]
R. Bhagwan, S. Savage, and G. M. Voelker, "Understanding availability," in Proc. IPTPS, Feb. 2003, pp. 256-267.
[5]
F. Boesch, D. Gross, and C. Suffel, "A coherent model for reliability of multiprocessor networks," IEEE Trans. Reliab., vol. 45, no. 4, pp. 678-684, Dec. 1996.
[6]
B. Bollobás, "The evolution of the cube," Combinatorial Math., pp. 91-97, 1983.
[7]
B. Bollobás, Random Graphs. Cambridge, U.K.: Cambridge University Press, 2001.
[8]
Y. D. Burtin, "Connection probability of a random subgraph of an n-dimensional cube," Probl. Inf. Transm., vol. 13, no. 2, pp. 147-152, Apr.-June 1977.
[9]
F. E. Bustamante and Y. Qiao, "Friendships that last: Peer lifespan and its role in P2P protocols," in Proc. Intl. Workshop on Web Content Caching and Distribution, Sep. 2003.
[10]
Y. Chawathe, S. Ratnasamy, L. Breslau, N. Lanham, and S. Shenker, "Making Gnutella-like P2P systems scalable," in Proc. ACM SIGCOMM , Aug. 2003, pp. 407-418.
[11]
J. Chen, I. A. Kanj, and G. Wang, "Hypercube network fault tolerance: A probabilistic approach," in Proc. ICPP, Aug. 2002.
[12]
B.-G. Chun, B. Zhao, and J. Kubiatowicz, "Impact of neighbor selection on performance and resilience of structured P2P networks," in Proc. IPTPS, Feb. 2005, pp. 264-274.
[13]
P. Erdös and A. Rényi, "On the evolution of random graphs," Publ. Math. Inst. Hungarian. Acad. Sci., vol. 5, pp. 17-61, 1960.
[14]
A.-H. Esfahanian, "Generalized measures of fault tolerance with application to n-cube networks," IEEE Trans. Comput., vol. 38, no. 11, pp. 1586-1591, Nov. 1989.
[15]
A. Feldmann, A. C. Gilbert, W. Willinger, and T. G. Kurtz, "The changing nature of network traffic: Scaling phenomena," in ACM SIGCOMM Comp. Comm. Rev., Apr. 1998, vol. 28, pp. 5-29.
[16]
H. Frank, "Maximally reliable node weighted graphs," in Proc. 3rd Ann. Conf. Information Sciences and Systems, Mar. 1969, pp. 1-6.
[17]
A. Ganesh and L. Massoulié, "Failure resilience in balanced overlay networks," in Proc. Allerton Conf. Commu. Contr. Comput., Oct. 2003.
[18]
Q.-P. Gu and S. Peng, "Unicast in hypercubes with a large number of faulty nodes," IEEE Trans. Parallel Distrib. Syst., vol. 10, no. 10, pp. 964-975, 1999.
[19]
K. Gummadi, R. Gummadi, S. Gribble, S. Ratnasamy, S. Shenker, and I. Stoica, "The impact of DHT routing geometry on resilience and proximity," in Proc. ACM SIGCOMM, Aug. 2003, pp. 381-394.
[20]
M. F. Kaashoek and D. Karger, "Koorde: A simple degree-optimal distributed hash table," in Proc. IPTPS, Feb. 2003, pp. 98-107.
[21]
A. K. Kelmans, "Connectivity of probabilistic networks," Auto. Remote Contr., vol. 29, pp. 444-460, 1967.
[22]
M. Kijima, Markov Processes for Stochastic Modeling. London, U.K.: Chapman & Hall, 1997.
[23]
S. Krishnamurthy, S. El-Ansary, E. Aurell, and S. Haridi, "A statistical theory of chord under churn," in Proc. IPTPS, Feb. 2005, pp. 93-103.
[24]
S. Latifi, "Combinatorial analysis of the fault diameter of the n-cube," IEEE Trans. Comput., vol. 42, no. 1, pp. 27-33, Jan. 1993.
[25]
D. Leonard, Z. Yao, X. Wang, and D. Loguinov, "On static and dynamic partitioning behavior of large-scale networks," in Proc. IEEE ICNP, Nov. 2005, pp. 345-357.
[26]
D. Liben-Nowell, H. Balakrishnan, and D. Karger, "Analysis of the evolution of the peer-to-peer systems," in Proc. ACMPODC, Jul. 2002, pp. 233-242.
[27]
D. Loguinov, A. Kumar, V. Rai, and S. Ganesh, "Graph-theoretic analysis of structured peer-to-peer systems: Routing distances and fault resilience," in Proc. ACM SIGCOMM, Aug. 2003, pp. 395-406.
[28]
G. S. Manku, M. Naor, and U. Weider, "Knowthy neighbor's neighbor: The power of lookahead in randomized P2P networks," in Proc. ACM STOC, Jun. 2004, pp. 54-63.
[29]
L. Massoulié, A.-M. Kermarrec, and A. Ganesh, "Network awareness and failure resilience in self-organising overlay networks," in Proc. IEEE SRDS, Oct. 2003, pp. 47-55.
[30]
C. D. Meyer, Matrix Analysis and Applied Linear Algebra. Philadelphia, PA: Society for Industrial and Applied Math, 2000.
[31]
W. Najjar and J.-L. Gaudiot, "Network resilience: A measure of network fault tolerance," IEEE Trans. Comput., vol. 39, no. 2, pp. 174-181, Feb. 1990.
[32]
G. Pandurangan, P. Raghavan, and E. Upfal, "Building low-diameter peer-to-peer networks," IEEE J. Sel. Areas Commun., vol. 21, no. 6, pp. 995-1002, Aug. 2003.
[33]
M. D. Penrose, "On k-connectivity for a geometric random graph," Random Structures & Algorithms, vol. 15, no. 2, pp. 145-164, Sep. 1999.
[34]
S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker, "A scalable content-addressable network," in Proc. ACM SIGCOMM, Aug. 2001, pp. 161-172.
[35]
S. Resnick, Adventures in Stochastic Processes. Boston, MA: Birkhäuser, 2002.
[36]
A. Rowstron and P. Druschel, "Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems," in Proc. IFIP/ACM International Conference on Distributed Systems Platforms (Middleware), Nov. 2001, pp. 329-350.
[37]
S. Saroiu, P. K. Gummadi, and S. D. Gribble, "A Measurement Study of peer-to-peer file sharing systems," in Proc. SPIE/ACM Multimedia Computing and Networking, Jan. 2002, vol. 4673, pp. 156-170.
[38]
I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan, "Chord: A scalable peer-to-peer lookup service for internet applications," in Proc. ACM SIGCOMM, Aug. 2001, pp. 149-160.
[39]
K. Sutner, A. Satyanarayana, and C. Suffel, "The complexity of the residual node connectedness reliability problem," SIAM J. Comput., vol. 20, pp. 149-155, 1991.
[40]
W. Wang, Y. Zhang, X. Li, and D. Loguinov, "On zone-balancing of peer-to-peer networks: Analysis of random node join," in ACM SIGMETRICS , Jun. 2004, pp. 211-222.
[41]
R. W. Wolff, Stochastic Modeling and the Theory of Queues. Englewood Cliffs, NJ: Prentice-Hall, 1989.
[42]
Z. Yao, X. Wang, D. Leonard, and D. Loguinov, "On node isolation under churn in unstructured P2P networks with heavy-tailed lifetimes," in Proc. IEEE INFOCOM, May 2007.
[43]
B. Y. Zhao, L. Huang, J. Stribling, S. C. Rhea, A. D. Joseph, and J. Kubiatowicz, "Tapestry: A resilient global-scale overlay for service deployment," IEEE J. Sel. Areas Commun., vol. 22, no. 1, pp. 41-53, Jan. 2004.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 16, Issue 6
December 2008
248 pages

Publisher

IEEE Press

Publication History

Published: 01 December 2008
Revised: 20 June 2006
Received: 26 January 2006
Published in TON Volume 16, Issue 6

Author Tags

  1. P2P
  2. churn
  3. dynamic resilience
  4. graph disconnection

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 12 Feb 2025

Other Metrics

Citations

Cited By

View all

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media