Top

Published in:

2019 | OriginalPaper | Chapter

Proportional Lumpability

Authors : Andrea Marin, Carla Piazza, Sabina Rossi

Published in: Formal Modeling and Analysis of Timed Systems

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We deal with the lumpability approach to cope with the state space explosion problem inherent to the computation of the performance indices of large stochastic models using a state aggregation technique. The lumpability method applies to Markov chains exhibiting some structural regularity and allows one to efficiently compute the exact values of the performance indices when the model is actually lumpable. The notion of quasi-lumpability is based on the idea that a Markov chain can be altered by relatively small perturbations of the transition rates in such a way that the new resulting Markov chain is lumpable. In this case only upper and lower bounds on the performance indices can be derived. In this paper we introduce a novel notion of quasi lumpability, named proportional lumpability, which extends the original definition of lumpability but, differently than the general definition of quasi lumpability, it allows one to derive exact performance indices for the original process.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Sandboxing Controllers for Stochastic Cyber-Physical Systems

next chapter Expected Reachability-Price Games

Alzetta, G., Marin, A., Piazza, C., Rossi, S.: Lumping-based equivalences in markovian automata: algorithms and applications to product-form analyses. Inf. Comput. 260, 99–125 (2018). https://doi.org/10.1016/j.ic.2018.04.002MathSciNetCrossRefMATH

Baarir, S., Beccuti, M., Dutheillet, C., Franceschinis, G.: From partially to fully lumped Markov chains in stochastic well formed Petri nets. In: Proceedings of Valuetools 2009 Conference, p. 44. ACM (2009). https://doi.org/10.4108/ICST.VALUETOOLS2009.7733

Baarir, S., Beccuti, M., Dutheillet, C., Franceschinis, G., Haddad, S.: Lumping partially symmetrical stochastic models. Perform. Eval. 68(1), 21–44 (2011). https://doi.org/10.1016/j.peva.2010.09.002CrossRef

Baarir, S., Dutheillet, C., Haddad, S., Iliè, J.M.: On the use of exact lumping in partially symmetrical Well-formed Petri Nets. In: Proceedings of International Conference on Quantitative Evaluation of Systems (QEST), Torino, Italy, pp. 23–32. IEEE Computer Society (2005). https://doi.org/10.1109/QEST.2005.26

Baier, C., Katoen, J.P., Hermanns, H., Wolf, V.: Comparative branching-time semantics for Markov chains. Inf. Comput. 200(2), 149–214 (2005). https://doi.org/10.1016/j.ic.2005.03.001MathSciNetCrossRefMATH

Balsamo, S., Marin, A.: Queueing networks. In: Bernardo, M., Hillston, J. (eds.) SFM 2007. LNCS, vol. 4486, pp. 34–82. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-72522-0_2CrossRef

Bernardo, M.: Weak Markovian bisimulation congruences and exact CTMC-level aggregations for concurrent processes. In: Proceedings of the 10th Workshop on Quantitative Aspects of Programming Languages and Systems (QALP 2012), pp. 122–136. EPTCS (2012). https://doi.org/10.4204/EPTCS.85.9CrossRef

Bernardo, M.: Weak Markovian bisimulation congruences and exact CTMC-level aggregations for sequential processes. In: Bruni, R., Sassone, V. (eds.) TGC 2011. LNCS, vol. 7173, pp. 89–103. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-30065-3_6CrossRef

Bravetti, M.: Revisiting interactive Markov chains. Electr. Notes Theor. Comput. Sci. 68(5), 65–84 (2003). https://doi.org/10.1016/S1571-0661(04)80520-6CrossRefMATH

10.

Buchholz, P.: Exact and ordinary lumpability in finite Markov chains. J. Appl. Probab. 31, 59–75 (1994). https://doi.org/10.1017/S0021900200107338MathSciNetCrossRefMATH

11.

Daly, D., Buchholz, P., Sanders, W.: Bound-preserving composition for Markov reward models. In: Third International Conference on the Quantitative Evaluation of Systems (QEST 2006), pp. 243–252 (2006). https://doi.org/10.1109/QEST.2006.8

12.

Franceschinis, G., Muntz, R.R.: Bounds for quasi-lumpable Markov chains. Perform. Eval. 20(1–3), 223–243 (1994). https://doi.org/10.1016/0166-5316(94)90015-9CrossRefMATH

13.

Franceschinis, G., Muntz, R.R.: Computing bounds for the performance indices of quasi-lumpable stochastic well-formed nets. IEEE Trans. Softw. Eng. 20(7), 516–525 (1994). https://doi.org/10.1109/32.297940CrossRefMATH

14.

Hermanns, H.: Interactive Markov Chains. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45804-2CrossRefMATH

15.

Hillston, J.: A Compositional Approach to Performance Modelling. Cambridge Press, Cambridge (1996)CrossRef

16.

Hillston, J., Marin, A., Piazza, C., Rossi, S.: Contextual lumpability. In: Proceedings of Valuetools 2013 Conference, pp. 194–203. ACM Press (2013). https://doi.org/10.4108/icst.valuetools.2013.254408

17.

Kemeny, J.G., Snell, J.L.: Finite Markov Chains. Springer, New York (1976)MATH

18.

Marin, A., Rossi, S.: Autoreversibility: exploiting symmetries in Markov chains. In: Proceedings of IEEE MASCOTS, San Francisco, CA, USA, pp. 151–160 (2013). https://doi.org/10.1109/MASCOTS.2013.23

19.

Marin, A., Rossi, S.: On the relations between Markov chain lumpability andreversibility. Acta Informatica 54(5), 447–485 (2017). https://doi.org/10.1007/s00236-016-0266-1MathSciNetCrossRefMATH

20.

Milios, D., Gilmore, S.: Component aggregation for PEPA models: an approach based on approximate strong equivalence. Perform. Eval. 94, 43–71 (2015). https://doi.org/10.1016/j.peva.2015.09.004CrossRef

21.

Molloy, M.K.: Performance analysis using stochastic Petri nets. IEEE Trans. Comput. 31(9), 913–917 (1982). https://doi.org/10.1109/TC.1982.1676110CrossRef

22.

Plateau, B.: On the stochastic structure of parallelism and synchronization models for distributed algorithms. SIGMETRICS Perform. Eval. Rev. 13(2), 147–154 (1985). https://doi.org/10.1145/317795.317819CrossRef

23.

Smith, M.: Compositional abstractions for long-run properties of stochastic systems. In: Eighth International Conference on Quantitative Evaluation of Systems, QEST 2011, pp. 223–232 (2011). https://doi.org/10.1109/QEST.2011.37

24.

Sumita, U., Reiders, M.: Lumpability and time-reversibility in the aggregation-disaggregation method for large Markov chains. Commun. Stat. Stoch. Model. 5, 63–81 (1989). https://doi.org/10.1080/15326348908807099MathSciNetCrossRefMATH

Title: Proportional Lumpability
Authors: Andrea Marin
Carla Piazza
Sabina Rossi
Publisher: Springer International Publishing
Book: Formal Modeling and Analysis of Timed Systems
Print ISBN: 978-3-030-29661-2

Electronic ISBN: 978-3-030-29662-9

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-030-29662-9_16

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner