Document Type
Conference Paper
Publication Date
3-2012
Publication Source
INFOCOM: 2012 Proceedings IEEE
Abstract
This paper builds a generic modeling framework for analyzing the edge-creation process in dynamic random graphs in which nodes continuously alternate between active and inactive states, which represent churn behavior of modern distributed systems. We prove that despite heterogeneity of node lifetimes, different initial out-degree, non-Poisson arrival/failure dynamics, and complex spatial and temporal dependency among creation of both initial and replacement edges, a superposition of edge-arrival processes to a live node under uniform selection converges to a Poisson process when system size becomes sufficiently large. Due to the convoluted dependency and non-renewal nature of various point processes, this result significantly advances classical Poisson convergence analysis and offers a simple analytical platform for future modeling of networks under churn in a wide range of degree-regular and -irregular graphs with arbitrary node lifetime distributions.
Inclusive pages
2991 - 2995
ISBN/ISSN
0743-166X
Document Version
Published Version
Copyright
Copyright © 2012 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works.
Publisher
IEEE
Place of Publication
Orlando, FL
Peer Reviewed
yes
Keywords
graph theory, stochastic processes, telecommunication network reliability, Poisson process, arbitrary node lifetime distributions, classical Poisson convergence analysis, convoluted dependency, degree-irregular graph, degree-regular graph, distributed systems, dynamic random graphs, edge-arrival process superposition, edge-creation process, generic modeling framework, heterogeneous edge process superposition, node lifetime heterogeneity, nonPoisson arrival-failure dynamics, nonrenewal nature, Ad hoc networks, Aggregates, Analytical models, Electronic mail, Peer to peer computing, Resilience, RoutingCouncils
eCommons Citation
Yao, Zhongmei; Cline, Daren B. H.; and Loguinov, Dmitri, "On Superposition of Heterogeneous Edge Processes in Dynamic Random Graphs" (2012). Computer Science Faculty Publications. 4.
https://ecommons.udayton.edu/cps_fac_pub/4
Included in
Databases and Information Systems Commons, Numerical Analysis and Scientific Computing Commons, OS and Networks Commons, Other Computer Sciences Commons, Theory and Algorithms Commons
Comments
Publisher Citation
Zhongmei Yao; Cline, D.B.H.; Loguinov, D., "On superposition of heterogeneous edge processes in dynamic random graphs," INFOCOM, 2012 Proceedings IEEE , vol., no., pp.2991,2995, 25-30 March 2012
Permission documentation is on file.