Abstract
Performance evaluation of computer software or hardware architectures may rely on the analysis of a complex stochastic model whose specification is usually given in terms of a high level formalism such as queueing networks, stochastic Petri nets, stochastic Automata or Markovian process algebras. Compositionality is a key-feature of many of these formalisms and allows the modeller to combine several (simple) components to form a complex architecture. However, although these formalisms allow for relative compact specifications of possibly complex models, the derivation of the interested performance indices may be very time and space consuming since the set of possible states of the model tends to grow exponentially with the number of components.
In this paper we focus on models with underlying continuous time Markov chains and we show sufficient conditions under which exact lumping of the forward or the reversed process can be derived, allowing the exact computation of marginal stationary probabilities of the cooperating components. The peculiarity of our method relies on the fact that lumping is applied at component-level rather than to the CTMC of the joint process, thus reducing both the memory requirement and the computational cost of the subsequent solution of the model.
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
This is a preview of subscription content, log in via an institution.
Buying options
Tax calculation will be finalised at checkout
Purchases are for personal use only
Learn about institutional subscriptionsPreview
Unable to display preview. Download preview PDF.
References
Balsamo, S., Iazeolla, G.: An extension of Norton’s theorem for queueing networks. IEEE Trans. on Software Eng. SE-8, 298–305 (1982)
Buchholz, P.: Adaptive decomposition and approximation for the analysis of stochastic Petri nets. Perf. Eval. 56, 23–52 (2004)
Buchholz, P.: Bounding stationary results of tandem networks with MAP input and MAP service time distributions. In: Proc. of ACM SIGMETRICS/PERFORMANCE, Saint Malo, FR, pp. 191–202 (2006)
Buchholz, P.: Product form approximations for communicating Markov processes. Perf. Eval. 67(9), 797–815 (2010), special Issue: QEST 2008
Chandy, K.M., Herzog, U., Woo, L.: Parametric analysis of queueing networks. IBM Journal of Res. and Dev. 1(1), 36–42 (1975)
Courtois, P.J., Semal, P.: Bounds for the positive eigenvectors of nonnegative matrices and for their approximations by decomposition. J. of the ACM 31(4), 804–825 (1984)
Courtois, P.: Decomposability. Academic Press, New York (1977)
Economou, A.: Generalized product-form stationary distributions for Markov chains in random environment with queueing application. Adv. in Appl. Prob. 37, 185–211 (2005)
Fourneau, J.M., Plateau, B., Stewart, W.J.: Product form for stochastic automata networks. In: ValueTools 2007: Proc. of the 2nd International Conference on Performance Evaluation Methodologies and Tools, pp. 1–10. ICST, Brussels (2007)
Franceschinis, G., Muntz, R.R.: Bounds for quasi-lumpable markov chains. Elsevier Perf. Eval. 20(1-3), 223–243 (1994)
Gelenbe, E.: Product form networks with negative and positive customers. J. of Appl. Prob. 28(3), 656–663 (1991)
Gilmore, S., Hillston, J.: The PEPA Workbench: A Tool to Support a Process Algebra Based Approach to Performance Modelling. In: Haring, G., Kotsis, G. (eds.) TOOLS 1994. LNCS, vol. 794, pp. 353–368. Springer, Heidelberg (1994)
Gilmore, S., Hillston, J., Ribaudo, M.: An Efficient Algorithm for Aggregating PEPA Models. IEEE Trans. on Software Eng. 27(5), 449–464 (2001)
Harrison, P.G.: Turning back time in Markovian process algebra. Theoretical Computer Science 290(3), 1947–1986 (2003)
Heindl, A.: Decomposition of general queueing networks with mmpp inputs and customer losses. Perf. Eval. 51(1-4), 117–136 (2003)
Hillston, J.: A Compositional Approach to Performance Modelling. Ph.D. thesis, Department of Computer Science, University of Edinburgh (1994)
Kelly, F.: Reversibility and stochastic networks. Wiley, New York (1979)
Kemeny, J.G., Snell, J.L.: Finite Markov Chains, ch. II. D. Van Nostrand Company, Inc. (1960)
Lavenberg, S.S.: Computer Performance Modeling Handbook. Academic Press, New York (1983)
Molloy, M.K.: Performance analysis using stochastic petri nets. IEEE Trans. on Comput. 31(9), 913–917 (1982)
Plateau, B.: On the stochastic structure of parallelism and synchronization models for distributed algorithms. SIGMETRICS Perform. Eval. Rev. 13(2), 147–154 (1985)
Stewart, G.: Computable error bounds for aggregated Markov chains. J. of the ACM 30(2), 271–285 (1983)
Stewart, W.J.: Introduction to the Numerical Solution of Markov Chains. Princeton University Press, UK (1994)
Valmari, A., Franceschinis, G.: Simple O(m logn) Time Markov Chain Lumping. In: Esparza, J., Majumdar, R. (eds.) TACAS 2010. LNCS, vol. 6015, pp. 38–52. Springer, Heidelberg (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Balsamo, S., Dei Rossi, GL., Marin, A. (2012). Lumping and Reversed Processes in Cooperating Automata. In: Al-Begain, K., Fiems, D., Vincent, JM. (eds) Analytical and Stochastic Modeling Techniques and Applications. ASMTA 2012. Lecture Notes in Computer Science, vol 7314. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-30782-9_15
Download citation
DOI: https://doi.org/10.1007/978-3-642-30782-9_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-30781-2
Online ISBN: 978-3-642-30782-9
eBook Packages: Computer ScienceComputer Science (R0)