Fluid computation of passage-time distributions in large Markov models.

*(English)*Zbl 1234.68318Summary: Recent developments in the analysis of large Markov models facilitate the fast approximation of transient characteristics of the underlying stochastic process. Fluid analysis makes it possible to consider previously intractable models whose underlying discrete state space grows exponentially as model components are added. In this work, we show how fluid-approximation techniques may be used to extract passage-time measures from performance models. We focus on two types of passage measure: passage times involving individual components, as well as passage times which capture the time taken for a population of components to evolve.

Specifically, we show that for models of sufficient scale, global passage-time distributions can be well approximated by a deterministic fluid-derived passage-time measure. Where models are not of sufficient scale, we are able to generate upper and lower approximations for the entire cumulative distribution function of these passage-time random variables, using moment-based techniques. Additionally, we show that, for passage-time measures involving individual components, the cumulative distribution function can be directly approximated by fluid techniques.

Finally, using the GPA tool, we take advantage of the rapid fluid computation of passage times to show how a multi-class client-server system can be optimised to satisfy multiple service level agreements.

Specifically, we show that for models of sufficient scale, global passage-time distributions can be well approximated by a deterministic fluid-derived passage-time measure. Where models are not of sufficient scale, we are able to generate upper and lower approximations for the entire cumulative distribution function of these passage-time random variables, using moment-based techniques. Additionally, we show that, for passage-time measures involving individual components, the cumulative distribution function can be directly approximated by fluid techniques.

Finally, using the GPA tool, we take advantage of the rapid fluid computation of passage times to show how a multi-class client-server system can be optimised to satisfy multiple service level agreements.

##### MSC:

68Q87 | Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) |

68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |

68Q85 | Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) |

##### Keywords:

fluid approximation; passage-time distribution; stochastic process algebra; service level agreement; scalability analysis
PDF
BibTeX
XML
Cite

\textit{R. A. Hayden} et al., Theor. Comput. Sci. 413, No. 1, 106--141 (2012; Zbl 1234.68318)

Full Text:
DOI

**OpenURL**

##### References:

[1] | Bradley, J.T.; Dingle, N.J.; Gilmore, S.T.; Knottenbelt, W.J., Derivation of passage-time densities in PEPA models using ipc: the imperial PEPA compiler, (), 344-351 |

[2] | Hayden, R.; Bradley, J.T., A fluid analysis framework for a Markovian process algebra, Theoretical computer science, 411, 2260-2297, (May 2010) |

[3] | Hillston, J., Fluid flow approximation of PEPA models, (), 33-43 |

[4] | Bortolussi, L.; Policriti, A., Stochastic concurrent constraint programming and differential equations, (), 27-42 · Zbl 1279.92031 |

[5] | Cardelli, L., From processes to ODEs by chemistry, () |

[6] | David, R.; Alla, H., Discrete, continuous, and hybrid Petri nets, (2010), Springer Berlin Heidelberg |

[7] | Benaïm, M.; Le Boudec, J.-Y., A class of Mean field interaction models for computer and communication systems, Performance evaluation, 65, 11-12, 823-838, (2008) |

[8] | Bobbio, A.; Gribaudo, M.; Telek, M., Analysis of large scale interacting systems by Mean field method, (), 215-224 |

[9] | Bakhshi, R.; Cloth, L.; Fokkink, W.; Haverkort, B.R., Mean-field framework for performance evaluation of push-pull gossip protocols, Performance evaluation, 68, 157-179, (February 2011) |

[10] | M. Tribastone, Scalable analysis of stochastic process algebra models, Ph.D. Thesis, University of Endinburgh, 2010. |

[11] | Little, J., A proof for the queuing formula: \(L = \lambda W\), Operations research, 9, 3, 383-387, (1961) · Zbl 0108.14803 |

[12] | J. Ding, Structural and fluid analysis for large scale PEPA models — with applications to content adaptation systems, Ph.D. Thesis, The University of Edinburgh, 2010. |

[13] | Clark, A.; Duguid, A.; Gilmore, S.T.; Tribastone, M., Partial evaluation of PEPA models for fluid-flow analysis, (), 2-16 |

[14] | G. Kesidis, T. Konstantopoulos, P. Sousi, A stochastic epidemiological model and a deterministic limit for BitTorrent-like peer-to-peer file-sharing networks, in: 2nd Workshop on Network Control and Optimization, NET-COOP, November 2008, pp. 26-36. · Zbl 1169.68316 |

[15] | J.T. Bradley, R. Hayden, W.J. Knottenbelt, T. Suto, Extracting response times from fluid analysis of performance models, in: SIPEW’08, SPEC International Performance Evaluation Workshop, Darmstadt, 27-28 June 2008, in: Lecture Notes in Computer Science, vol. 5119, May 2008, pp. 29-43. |

[16] | Dingle, N.J.; Knottenbelt, W.J., Automated customer-centric performance analysis of generalised stochastic Petri nets using tagged tokens, (), 75-88 |

[17] | G. Balbo, M. Beccuti, M. De Pierro, G. Franceschinis, First passage time computation in tagged GSPNs with queue places, The Computer Journal, July 2010, doi:10.1093/comjnl/bxq056. |

[18] | A. Stefanek, R.A. Hayden, J.T. Bradley, A new tool for the performance analysis of massively parallel computer systems, in: QAPL’10, 8th Workshop on Quantitative Aspects of Programming Languages, Electronic Proceedings of Theoretical Computer Science, vol. 28, 2010, pp. 159-181. |

[19] | Hillston, J., A compositional approach to performance modelling, (1996), Cambridge University Press |

[20] | Gilmore, S.; Hillston, J.; Ribaudo, M., An efficient algorithm for aggregating PEPA models, IEEE transactions on software engineering, 27, 449-464, (May 2001) |

[21] | Bradley, J.T.; Gilmore, S.T.; Hillston, J., Analysing distributed Internet worm attacks using continuous state-space approximation of process algebra models, Journal of computer and system sciences, 74, 1013-1032, (September 2008) |

[22] | Geisweiller, N.; Hillston, J.; Stenico, M., Relating continuous and discrete PEPA models of signalling pathways, Theoretical computer science, 404, 97-111, (November 2008) |

[23] | Júlvez, J.; Jiménez, E.; Recalde, L.; Silva, M., On observability in timed continuous Petri net systems, (), 60-69 |

[24] | Miller, R.K.; Michel, A.N., Ordinary differential equations, (1982), Academic Press · Zbl 0499.34024 |

[25] | Gillespie, C.S., Moment-closure approximations for mass-action models, IET systems biology, 3, 52-58, (January 2009) |

[26] | Lee, C.H.; Kim, K.-H.; Kim, P., A moment closure method for stochastic reaction networks, The journal of chemical physics, 130, (April 2009), pp. 134107-134107-15 |

[27] | J. Hespanha, Moment closure for biochemical networks, in: Communications, Control and Signal Processing, 2008. ISCCSP 2008. 3rd International Symposium on, March 2008, pp. 142-147. |

[28] | Dingle, N.J.; Harrison, P.G.; Knottenbelt, W.J., Uniformization and hypergraph partitioning for the distributed computation of response time densities in very large Markov models, Journal of parallel and distributed computing, 64, 908-920, (August 2004) |

[29] | C. Baier, B.R. Haverkort, H. Hermanns, J.-P. Katoen, Model checking continuous-time Markov chains by transient analysis, in: 12th International Conference on Computer Aided Verification, July 2000, pp. 358-372. · Zbl 0974.68017 |

[30] | Shwartz, A.; Weiss, A., Large deviations for performance analysis, (1995), Chapman and Hall |

[31] | R.A. Hayden, Ph.D. Thesis additional material. http://rhayden.me.uk/thesis, 2011. |

[32] | Tari, A.; Telek, M.; Buchholz, P., A unified approach to the moments based distribution estimation — unbounded support, (), 79-93 |

[33] | Le Boudec, J.-Y., Performance evaluation of computer and communication systems, (2010), EPFL Press Lausanne, Switzerland · Zbl 1246.68004 |

[34] | Serfozo, R., Basics of applied stochastic processes, (2009), Springer Berlin Heidelberg · Zbl 1159.60001 |

[35] | Tribastone, M.; Gilmore, S.T.; Hillston, J., Scalable differential analysis of process algebra models, IEEE transactions on software engineering, PP, 99, 1, (2010) |

[36] | Kurtz, T., Solutions of ordinary differential equations as limits of pure jump Markov processes, vol. 7, (April 1970), pp. 49-58 |

[37] | Darling, R.W.R.; Norris, J.R., Differential equation approximations for Markov chains, Probability surveys, 5, 37, (2008) · Zbl 1189.60152 |

[38] | Benaïm, M., Recursive algorithms, urn processes and chaining number of chain recurrent sets, Ergodic theory and dynamical systems, 18, 1, 53-87, (1998) · Zbl 0921.60061 |

[39] | Kurtz, T.; Ethier, S., Markov processes characterisation and convergence, (1986), Wiley |

[40] | R.A. Hayden, Scalable performance analysis of massively parallel stochastic systems. Ph.D. Thesis, Imperial College London, 2011. http://pubs.doc.ic.ac.uk/hayden-thesis. |

[41] | Scott, J.K.; Barton, P.I., Tight, efficient bounds on the solutions of chemical kinetics models, Computers & chemical engineering, 34, 717-731, (May 2010) |

[42] | Silva, M.; Terue, E.; Colom, J., Linear algebraic and linear programming techniques for the analysis of place/transition net systems, (), 309-373 · Zbl 0926.68086 |

[43] | Ben-Israel, A.; Greville, T.N.E., Generalized inverses: theory and applications, (2003), Springer · Zbl 1026.15004 |

[44] | Khalil, H.K., Nonlinear systems, (2002), Prentice Hall · Zbl 0626.34052 |

[45] | A. Pavlov, N. van de Wouw, H. Nijmeijer, Convergent piecewise affine systems: analysis and design, Part I: continuous case, in: 44th IEEE Conference on Decision and Control, CDC-ECC ’05, December 2005, pp. 5391-5396. |

[46] | S. Boyd, L. El Ghaoui, E. Feron, V. Balakrishnan, Linear matrix inequalities in system and control theory. Society for Industrial and Applied Mathematics, 1994. · Zbl 0816.93004 |

[47] | The MathWorks, Introduction to linear matrix inequalities (Robust Control Toolbox™). http://www.mathworks.com/access/helpdesk/help/toolbox/robust/ug/f8-2138.html. |

[48] | Johansson, M.; Rantzer, A., Computation of piecewise quadratic Lyapunov functions for hybrid systems, IEEE transactions on automatic control, 43, 555-559, (April 1998) |

[49] | Brin, M.; Stuck, G., Introduction to dynamical systems, (2002), Cambridge University Press · Zbl 1314.37002 |

[50] | Billingsley, P., Convergence of probability measures, (1968), John Wiley & Sons · Zbl 0172.21201 |

[51] | Kallenberg, O., Foundations of modern probability, (2002), Springer · Zbl 0996.60001 |

[52] | Rogers, L.C.G.; Williams, D., Diffusions, Markov processes and martingales, volume 1: foundations, (2000), Cambridge University Press · Zbl 0949.60003 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.