Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-28T05:55:48.641Z Has data issue: false hasContentIssue false
  • English
  • Français

A Scaling Analysis of a Transient Stochastic Network

Part of: Computer system organization Operations research and management science Limit theorems Special processes

Published online by Cambridge University Press:  22 February 2016

Mathieu Feuillet  and
Philippe Robert
Mathieu Feuillet*
Affiliation:
INRIA-Rocquencourt
Philippe Robert*
Affiliation:
INRIA-Rocquencourt
*
∗ Postal address: INRIA-Rocquencourt, Domaine de Voluceau, 78153 Le Chesnay, France.
∗ Postal address: INRIA-Rocquencourt, Domaine de Voluceau, 78153 Le Chesnay, France.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In this paper we use a simple transient Markov process with an absorbing point to investigate the qualitative behavior of a large-scale storage network of nonreliable file servers across which files can be duplicated. When the size of the system goes to ∞, we show that there is a critical value for the maximum number of files per server such that, below this quantity, most files have a maximum number of copies. Above this value, the network loses a significant number of files until some equilibrium is reached. When the network is stable, we show that, with convenient time scales, the evolution of the network towards the absorbing state can be described via a stochastic averaging principle.

Keywords

Distributed system with breakdowntime scaletransient Markov chain with absorbing stateSkorokhod problem

MSC classification

Primary: 60K25: Queueing theory 60F05: Central limit and other weak theorems
Secondary: 68M14: Distributed systems 90B05: Inventory, storage, reservoirs
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 46 , Issue 2 , June 2014 , pp. 516 - 535
Copyright
© Applied Probability Trust 

References

Anderson, R. F. and Orey, S. (1976). Small random perturbation of dynamical systems with reflecting boundary. Nagoya Math. J. 60, 189–216.CrossRefGoogle Scholar
Artalejo, J. R. and Gómez-Corral, A. (2008). Retrial Queueing Systems. A Computational Approach. Springer, Berlin.Google Scholar
Billingsley, P. (1999). Convergence of Probability Measures, 2nd edn. John Wiley, New York.Google Scholar
Brown, T. (1978). A martingale approach to the Poisson convergence of simple point processes. Ann. Prob. 6, 615–628.Google Scholar
Chun, B.-G. et al. (2006). Efficient replica maintenance for distributed storage systems. In Proc. NSDI, IEEE, pp. 45–58.Google Scholar
Darroch, J. N. and Seneta, E. (1965). On quasi-stationary distributions in absorbing discrete-time finite Markov chains. J. Appl. Prob. 2, 88–100.Google Scholar
Dawson, D. A. (1993). Measure-Valued Markov Processes. In École d'Été de Probabilités de Saint-Flour XXI—1991 (Lecture Notes Math. 1541), Springer, Berlin, pp. 1–260.Google Scholar
El Karoui, N. and Chaleyat-Maurel, M. (1978). Temps Locaux, vol. 52-53, ch. Un problème de réflexion et ses applications au temps local et aux équations différentielles stochastiques sur R-cas continu. In Astärisque (Temps Locaux 52–53), Société Mathématique de France, pp. 117–144.Google Scholar
Ethier, S. N. and Kurtz, T. G. (1986). Markov Processes: Characterization and Convergence. John Wiley, New York.Google Scholar
Falin, G. I. and Templeton, J. G. C. (1997). Retrials Queues. Chapman & Hall, London.Google Scholar
Ferrari, P. A., Kesten, H., Martinez, S. and Picco, P. (1995). Existence of quasi-stationary distributions. A renewal dynamical approach. Ann. Prob. 23, 501–521.Google Scholar
Feuillet, M. (2012). On the flow-level stability of data networks without congestion control: the case of linear networks and upstream trees. Queueing Systems 70, 105–143.CrossRefGoogle Scholar
Feuillet, M. and Robert, P. (2012). On the transient behavior of Ehrenfest and Engset processes. Adv. Appl. Prob. 44, 562–582.Google Scholar
Freidlin, M. I. and Wentzell, A. D. (1998). Random Perturbations of Dynamical Systems, 2nd edn. Springer, New York.CrossRefGoogle Scholar
Guckenheimer, J. and Holmes, P. (1990). Nonlinear Oscillations, Dynamical Systems, and Bifurcations of Vector Fields. (Appl. Math. Sci. 42). Springer, New York.Google Scholar
Harrison, J. M. and Reiman, M. I. (1981). Reflected Brownian motion on an orthant. Ann. Prob. 9, 302–308.Google Scholar
Has'minskiī, R. Z. (1980). Stochastic Stability of Differential Equations. Sijthoff & Noordhoff, Alphen aan den Rijn, Germantown, MD.Google Scholar
Hunt, P. J. and Kurtz, T. G. (1994). Large loss networks. Stoch. Process. Appl. 53, 363–378.Google Scholar
Kasahara, Y. and Watanabe, S. (1986). Limit theorems for point processes and their functionals. J. Math. Soc. Japan 38, 543–574.Google Scholar
Kelly, F. P. (1991). Loss networks. Ann. Appl. Prob. 1, 319–378.Google Scholar
King, P. J. B. (1990). Computer and Communication Systems Performance Modelling. Prentice Hall, London.Google Scholar
Kurtz, T. G. (1992). Averaging for Martingale Problems and Stochastic Approximation. In Applied Stochastic Analysis (Lecture Notes Control Inf. Sci. 177), Springer, Berlin, pp. 186–209.Google Scholar
Legtchenko, S., Monnet, S., Sens, P. and Muller, G. (2011). RelaxDHT: a churn-resilient replication strategy for peer-to-peer distributed hash-tables. ACM Trans. Autonomous Adaptive Systems 7, 28.Google Scholar
Papanicolaou, G. C., Stroock, D. and Varadhan, S. R. S. (1977). Martingale approach to some limit theorems. In Papers from the Duke Turbulence Conference (Duke University, Durham, NC, 1976), Paper number 6.Google Scholar
Pavliotis, G. A. and Stuart, A. M. (2008). Multiscale Methods. Averaging and Homogenization. (Texts Appl. Math. 53). Springer, New York.Google Scholar
Perry, O. and Whitt, W. (2011). An ODE for an overloaded X model involving a stochastic averaging principle. Stoch. Systems 1, 59–108.Google Scholar
Picconi, F., Baynat, B. and Sens, P. (2007). An Analytical Estimation of Durability in DHTs. In Distributed Computing and Internet Technology (Lecture Notes Comput. Sci. 4882), Springer, Berlin, pp. 184–196.Google Scholar
Ramabhadran, S. and Pasquale, J. (2006). Analysis of long-running replicated systems. In Proc. INFOCOM 2006, IEEE, pp. 1–9.Google Scholar
Ramanan, K. (2006). Reflected diffusions defined via the extended Skorokhod map. Electron. J. Prob. 11, 934–992.Google Scholar
Rhea, S. et al. (2005). OpenDHT: a public DHT service and its uses. In Proc. SIGCOMM '05, ACM, New York, pp. 73–84.CrossRefGoogle Scholar
Robert, P. (2003). Stochastic Networks and Queues. (Appl. Math. (New York) 52). Springer, Berlin.Google Scholar
Rowstron, A. and Druschel, P. (2001). Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility. In Proc. SOSP'01, ACM, New York, pp. 188–201.Google Scholar
Rudin, W. (1987). Real and Complex Analysis, 3rd edn. McGraw-Hill, New York.Google Scholar
Skorokhod, A. V. (1962). Stochastic equations for diffusion processes in a bounded region. II. Theory Prob. Appl. 7, 3–23.Google Scholar
Taylor, L. M. and Williams, R. J. (1993). Existence and uniqueness of semimartingale reflecting Brownian motions in an orthant. Prob. Theory Relat. Fields 96, 283–317.Google Scholar