Nothing Special   »   [go: up one dir, main page]

Skip to main content

Solving Large Markov Models Described with Standard Programming Language

  • Conference paper
  • First Online:
Computer and Information Sciences (ISCIS 2018)

Part of the book series: Communications in Computer and Information Science ((CCIS,volume 935))

Included in the following conference series:

  • 616 Accesses

Abstract

Continuous time Markov chains (CTMC) are one of the formalisms for building models. This paper discusses OLYMP2 - a system for solving big CTMC models (exceeding \(10^9\) states), described with a standard programming language - Java. OLYMP2 is primarily aimed at modelling of computer networks, so its formalism comes from networking concepts, like queueing systems. Using Java as a model description allows for greater flexibility in comparison to model-checker specific languages that often do not employ complete features of an object-oriented programming. Using Java also makes the parsing of models relatively fast, due to optimised Java run-time environment. Introducing dedicated compression of transition matrices allows for keeping memory usage at reasonable level even for large models.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Baier, C., Katoen, J.-P.: Principles of Model Checking. The MIT Press, Cambridge (2008). ISBN-13:978-0-262-02649-9

    Google Scholar 

  2. Behrmann, G., David, A., Larsen, K.G.: A tutorial on Uppaal. In: Bernardo, M., Corradini, F. (eds.) SFM-RT 2004. LNCS, vol. 3185, pp. 200–236. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30080-9_7

    Chapter  Google Scholar 

  3. Czachórski, T., Grochla, K., Józefiok, A., Nycz, T.: Simulation, markov chain and diffusion approximation models–a case study. In: Computer Science & Information Technologies (CSIT2011) (2011)

    Google Scholar 

  4. Erlang, A.: Solution of some problems in the theory of probabilities of significance in automatic telephone exchanges, post office. Electr. Eng. J. 10, 189–197 (1918)

    Google Scholar 

  5. Fourneau, J.M., Mahjoub, Y.A.E., Quessette, F., Vekris, D.: XBorne 2016: a brief introduction. In: Czachórski, T., Gelenbe, E., Grochla, K., Lent, R. (eds.) ISCIS 2016. CCIS, vol. 659, pp. 134–141. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-47217-1_15

    Chapter  Google Scholar 

  6. Hansson, H., Jonsson, B.: A logic for reasoning about time and reliability. Form. Asp. Comput. 6(5), 512–535 (1994)

    Article  Google Scholar 

  7. Holzmann, G.J.: The Spin Model Checker: Primer and Reference Manual, 4th edn. Addison-Wesley, Boston (2008). OCLC:254420839

    Google Scholar 

  8. Kirschnick, M.: The performance evaluation and prediction system for queueing networks-PEPSY-QNS. Technical Report TR-I4-18-94, Department of Computer Science 4, Universität Erlangen-Nürnberg, Germany (1994)

    Google Scholar 

  9. Krieger, U.R., Muller-Clostermann, B., Sczittnick, M.: Modeling and analysis of communication systems based on computational methods for markov chains. IEEE J. Sel. Areas Commun. 8(9), 1630–1648 (1990)

    Article  Google Scholar 

  10. Nowak, M., Pecka, P.: Reducing the number of states for markovian model of optical slotted ring network. In: Balandin, S., Dunaytsev, R., Koucheryavy, Y. (eds.) NEW2AN/ruSMART -2010. LNCS, vol. 6294, pp. 231–241. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14891-0_21

    Chapter  Google Scholar 

  11. Parzen, E.: Stochastic Processes. Classics in applied mathematics. Society for Industrial and Applied Mathematics (1999)

    Google Scholar 

  12. Pecka, P.: Obiektowo zorientowany wielowątkowy system do modelowania stanów nieustalonych w sieciach komputerowych za pomocą łanńcuchów Markowa (in Polish). PhD thesis, IITiS PAN, Gliwice (2002)

    Google Scholar 

  13. Pecka, P., Deorowicz, S., Nowak, M.: Efficient representation of transition matrix in the markov process modeling of computer networks. In: Kacprzyk, J., Czachórski, T., Kozielski, S., Stańczyk, U. (eds.) Man-Machine Interactions 2, vol. 103, pp. 457–464. Springer, Berlin (2011)

    Google Scholar 

  14. Rataj, A.: More flexible models using a new version of the translator of Java sources to timed automatons J2tadd. Theor. Appl. Inform. 21(2), 107–114 (2009)

    Google Scholar 

  15. Rataj, A., Woźna, B., Zbrzezny, A.: A translator of java programs to TADDs. Fundam. Inf. 93(1–3), 305–324 (2009)

    MathSciNet  MATH  Google Scholar 

  16. Stewart, W.J.: Introduction to the Numerical Solution of Markov Chains. Princeton University Press, Princeton (1994)

    Google Scholar 

  17. Visser, W., Pasareanu, C.S., Khurshid, S.: Test input generation with java PathFinder. ACM SIGSOFT Softw. Eng. Notes 29(4), 97 (2004)

    Article  Google Scholar 

  18. Zbrzezny, A., Woźna, B.: Towards verification of Java programs in VerICS. Fundam. Inform. 85(1–4), 533–548 (2008)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to P. Pecka .

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2018 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Pecka, P., Nowak, M.P., Rataj, A., Nowak, S. (2018). Solving Large Markov Models Described with Standard Programming Language. In: Czachórski, T., Gelenbe, E., Grochla, K., Lent, R. (eds) Computer and Information Sciences. ISCIS 2018. Communications in Computer and Information Science, vol 935. Springer, Cham. https://doi.org/10.1007/978-3-030-00840-6_7

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-00840-6_7

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-00839-0

  • Online ISBN: 978-3-030-00840-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics