Performance evaluation in stochastic process algebra dtsdPBC

I. V. Tarasyuk

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 18 (2021) no. 2, pp. 1105-1145.

Résumé

We consider discrete time stochastic and deterministic Petri box calculus (dtsdPBC), recently proposed by I.V. Tarasyuk. dtsdPBC is a discrete time extension with stochastically and deterministically timed multiactions of the well-known Petri box calculus (PBC), presented by E. Best, R. Devillers, J.G. Hall and M. Koutny. In dtsdPBC, stochastic multiactions have (conditional) probabilities of execution at the next time moment while deterministic multiactions have non-negative integers associated that specify fixed (including zero) delays. dtsdPBC features a step operational semantics via labeled probabilistic transition systems. In order to evaluate performance in dtsdPBC, the underlying semi-Markov chains (SMCs) are investigated, which are extracted from the transition systems corresponding to the process expressions of the calculus. It is demonstrated that the performance analysis in dtsdPBC is alternatively possible by exploring the corresponding discrete time Markov chains (DTMCs) and their reductions (RDTMCs), obtained by eliminating the states with zero residence time (vanishing states). The method based on DTMCs permits to avoid building the embedded DTMC (EDTMC) and weighting the probability masses in the states by their average sojourn times. The method based on RDTMCs simplifies performance analysis of large systems due to eliminating the non-stop transit (vanishing) states where only instantaneous activities are executed, resulting in a smaller model that can easier be solved directly.

Détail

Keywords: stochastic process algebra, Petri box calculus, discrete time, deterministic multiaction, transition system, operational semantics, performance evaluation, reduction.
Mots-clés : stochastic multiaction, Markov chain

Bibliographie

[1] W.M.P. van der Aalst, K.M. van Hee, H.A. Reijers, “Analysis of discrete-time stochastic Petri nets”, Stat. Neerl., 54:2 (2000), 237–255 | DOI | Zbl

[2] G. Balbo, “Introduction to stochastic Petri nets”, Lect. Notes Comput. Sci., 2090, Springer, Berlin, 2001, 84–155 | DOI | Zbl

[3] G. Balbo, “Introduction to generalized stochastic Petri nets”, Lect. Notes Comput. Sci., 4486, Springer, Berlin, 2007, 83–131 | DOI | Zbl

[4] E. Bartocci, P. Lió, “Computational modeling, formal analysis, and tools for systems biology”, PLoS Computational Biology, 12:1 (2016), e1004591 | DOI

[5] F. Bause, P.S. Kritzinger, Stochastic Petri nets. An introduction to the theory, Vieweg, Wiesbaden, 2002 | Zbl

[6] J.A. Bergstra, J.W. Klop, “Algebra of communicating processes with abstraction”, Theor. Comput. Sci., 37 (1985), 77–121 | DOI | Zbl

[7] M. Bernardo, M. Bravetti, Reward based congruences: Can we aggregate more?, Lect. Notes in Comput. Sci., 2165, 2001, 136–151 | DOI | Zbl

[8] M. Bernardo, R. Gorrieri, “A tutorial on EMPA: A theory of concurrent processes with nondeterminism, priorities, probabilities and time”, Theor. Comput. Sci., 202:1–2 (1998), 1–54 | DOI | Zbl

[9] E. Best, R. Devillers, J.G. Hall, “The box calculus: a new causal algebra with multi-label communication”, Lect. Notes Comput. Sci., 609, Springer, Berlin, 1992, 21–69 | DOI | MR

[10] E. Best, R. Devillers, M. Koutny, Petri net algebra, EATCS Monographs in Theoretical Computer Science, Springer, Berlin, 2001 | DOI | Zbl

[11] E. Best, M. Koutny, “A refined view of the box algebra”, Lect. Notes Comput. Sci., 935, Springer, Berlin, 1995, 1–20 | DOI | MR

[12] T. Bolognesi, F. Lucidi, S. Trigila, “From timed Petri nets to timed LOTOS”, Proc. IFIP WG 6.1 $10^{th}$ Int. Symposium on Protocol Specification, Testing and Verification (1990, Ottawa, Canada), North-Holland, Amsterdam, 1990, 1–14

[13] N. Bonzanni, K.A. Feenstra, W. Fokkink, E. Krepska, What can formal methods bring to systems biology?, Lect. Notes Comput. Sci., 5850, Springer, Berlin, 2009, 16–22 | DOI

[14] A.A. Borovkov, Probability theory, Universitext (UTX) series, Springer, London, 2013 | DOI | Zbl

[15] G. Chiola, “A software package for the analysis of generalized stochastic Petri net models”, Proc. $1^{st}$ Int. Workshop on Timed Petri Nets (July, 1985), 136–143

[16] G. Ciardo, J.K. Muppala, K.S. Trivedi, “SPNP: stochastic Petri net package”, Proc. $3^{rd}$ Int. Workshop on Petri Nets and Performance Models (PNPM), 1989, 142–151

[17] G. Ciardo, J.K. Muppala, K.S. Trivedi, “On the solution of GSPN reward models”, Perform. Eval., 12:4 (1991), 237–253 | DOI | Zbl

[18] M. Coderch, A.S. Willsky, S.S. Sastry, D.A. Castanon, “Hierarchical aggregation of singularly perturbed finite state Markov processes”, Stochastics, 8:4 (1983), 259–289 | DOI | Zbl

[19] R.J. van Glabbeek, “The linear time – branching time spectrum II: the semantics of sequential systems with silent moves. Extended abstract”, Lect. Notes Comput. Sci., 715, Springer, Berlin, 1993, 66–81 | DOI

[20] H.M. Hanisch, “Analysis of place/transition nets with timed arcs and its application to batch process control”, Lect. Notes Comput. Sci., 691, Springer, Berlin, 1993, 282–299 | DOI | MR

[21] B.R. Haverkort, “Markovian models for performance and dependability evaluation”, Lect. Notes Comput. Sci., 2090, Springer, Berlin, 2001, 38–83 | DOI | Zbl

[22] H. Hermanns, M. Rettelbach, “Syntax, semantics, equivalences and axioms for MTIPP”, Arbeitsberichte des IMMD, 27:4, Proc. of PARM 1994 (1994), 71–88

[23] J. Hillston, A compositional approach to performance modelling, Distinguished Dissertations in Computer Science, 12, Cambridge University Press, Cambridge, 1996 | Zbl

[24] C.A.R. Hoare, Communicating sequential processes, Prentice-Hall, New Jersey etc, 1985 | Zbl

[25] J.-P. Katoen, Quantinative and qualitative extensions of event structures, Ph.D. thesis, CTIT Ph.D.-thesis series, No 96–09, Centre for Telematics and Information Technology, University of Twente, Enschede, The Netherlands, 1996

[26] M. Koutny, “A compositional model of time Petri nets”, Lect. Notes Comput. Sci., 1825, Springer, Berlin, 2000, 303–322 | DOI | Zbl

[27] V.G. Kulkarni, Modeling and analysis of stochastic systems, CRC Press, Boca Raton, 2010 | Zbl

[28] L. Lakatos, L. Szeidl, M. Telek, Introduction to queueing systems with telecommunication applications, Springer, Cham, 2019 | Zbl

[29] H. Macià, V. Valero, D.C. Cazorla, F. Cuartero, “Introducing the iteration in sPBC”, Lect. Notes Comput. Sci., 3235, Springer, Berlin, 2004, 292–308 | DOI | Zbl

[30] H. Macià, V. Valero, F. Cuartero, D. de Frutos, “A congruence relation for sPBC”, Form. Methods Syst. Des., 32:2 (2008), 85–128 | DOI | Zbl

[31] H. Macià, V. Valero, F. Cuartero, M.C. Ruiz, “sPBC: a Markovian extension of Petri box calculus with immediate multiactions”, Fundam. Inform., 87:3–4 (2008), 367–406 | Zbl

[32] H. Macià, V. Valero, F. Cuartero, M.C. Ruiz, I.V. Tarasyuk, “Modelling a video conference system with sPBC”, Appl. Math. Inf. Sci., 10:2 (2016), 475–493 | DOI

[33] H. Macià, V. Valero, D. de Frutos, “sPBC: a Markovian extension of finite Petri box calculus”, Proc. $9^{th}$ IEEE Int. Workshop on Petri Nets and Performance Models (PNPM) (2001, Aachen, Germany), IEEE Computer Society Press, 2001, 207–216 | DOI

[34] J. Markovski, A. Sokolova, N. Trčka, E.P. de Vink, “Compositionality for Markov reward chains with fast and silent transitions”, Performance Evaluation, 66:8 (2009), 435–452 | DOI

[35] O. Marroquín, D. de Frutos, TPBC: timed Petri box calculus, Technical Report, Departamento de Sistemas Infofmáticos y Programación, Universidad Complutense de Madrid, Spain, 2000 (in Spanish)

[36] O. Marroquín, D. de Frutos, “Extending the Petri box calculus with time”, Lect. Notes Comput. Sci., 2075, Springer, Berlin, 2001, 303–322 | DOI | Zbl

[37] M.A. Marsan, “Stochastic Petri nets: an elementary introduction”, Lect. Notes Comput. Sci., 424, Springer, Berlin, 1990, 1–29 | DOI

[38] M.A. Marsan, G. Balbo, G. Conte, S. Donatelli, G. Franceschinis, Modelling with generalised stochastic Petri nets, Wiley Series in Parallel Computing, John Wiley and Sons, Chichester, 1995 | Zbl

[39] Ph.M. Merlin, D.J. Farber, “Recoverability of communication protocols – implications of a theoretical study”, IEEE Trans. Commun., 24:9 (1976), 1036–1043 | DOI | Zbl

[40] R.A.J. Milner, Communication and concurrency, Prentice Hall, New York etc, 1989 | Zbl

[41] M.K. Molloy, On the integration of the throughput and delay measures in distributed processing models, Ph.D. thesis, Report, No CSD-810-921, University of California, Los Angeles, CA, USA, 1981, 108 pp.

[42] M.K. Molloy, “Discrete time stochastic Petri nets”, IEEE Trans. Software Eng., 11:4 (1985), 417–423 | DOI | Zbl

[43] T.N. Mudge, H.B. Al-Sadoun, “A semi-Markov model for the performance of multiple-bus systems”, IEEE Transactions on Computers, C-34:10 (1985), 934–942 | DOI

[44] A. Niaouris, “An algebra of Petri nets with arc-based time restrictions”, Lect. Notes Comput. Sci., 3407, Springer, Berlin, 2005, 447–462 | DOI | Zbl

[45] A. Niaouris, M. Koutny, An algebra of timed-arc Petri nets, Technical Report, No CS-TR-895, School of Computer Science, University of Newcastle upon Tyne, UK, 2005

[46] C. Ramchandani, Performance evaluation of asynchronous concurrent systems by timed Petri nets, Ph.D. thesis, Department of Electrical Engineering, Massachusetts Institute of Technology, Cambridge, Massachusetts, USA, 1973

[47] S.M. Ross, Stochastic processes, John Wiley Sons, New York, 1996 | Zbl

[48] I.V. Tarasyuk, Discrete time stochastic Petri box calculus, Berichte aus dem Department für Informatik, No 3/05, Carl von Ossietzky Universität, Oldenburg, Germany, 2005

[49] I.V. Tarasyuk, “Iteration in discrete time stochastic Petri box calculus”, Jt. Bull. NCC IIS, Ser. Comput. Sci., 24 (2006), 129–148 | Zbl

[50] I.V. Tarasyuk, “Stochastic Petri box calculus with discrete time”, Fundam. Inform., 76:1–2 (2007), 189–218 | Zbl

[51] I.V. Tarasyuk, “Equivalence relations for modular performance evaluation in dtsPBC”, Math. Struct. Comput. Sci., 24:1 (2014), e240103 | DOI | Zbl

[52] I.V. Tarasyuk, “Discrete time stochastic and deterministic Petri box calculus dtsdPBC”, Sib. Électron. Mat. Izv., 17 (2020), 1598–1679 | DOI | Zbl

[53] I.V. Tarasyuk, H. Macià, V. Valero, Discrete time stochastic Petri box calculus with immediate multiactions, Technical Report, No DIAB-10-03-1, Department of Computer Systems, High School of Computer Science Engineering, University of Castilla, La Mancha, Albacete, Spain, 2010, 25 pp.

[54] I.V. Tarasyuk, H. Macià, V. Valero, “Discrete time stochastic Petri box calculus with immediate multiactions dtsiPBC”, Electronic Notes in Theoretical Computer Science, 296 (2013), 229–252 | DOI

[55] I.V. Tarasyuk, H. Macià, V. Valero, “Performance analysis of concurrent systems in algebra dtsiPBC”, Programm. Comput. Softw., 40:5 (2014), 229–249 | DOI | Zbl

[56] I.V. Tarasyuk, H. Macià Soler, V. Valero Ruiz, “Stochastic equivalence for performance analysis of concurrent systems in dtsiPBC”, Sib. Électron. Mat. Izv., 15 (2018), 1743–1812 | DOI | Zbl

[57] K.S. Trivedi, Probability and statistics with reliability, queuing, and computer science applications, John Wiley Sons, Hoboken, 2016 | Zbl

[58] V. Valero, M.E. Cambronero, “Using unified modelling language to model the publish/subscribe paradigm in the context of timed Web services with distributed resources”, Math. Comput. Model. Dyn. Syst., 23:6 (2017), 570–594 | DOI

[59] R. Zijal, “Discrete time deterministic and stochastic Petri nets”, Quality of communication-based systems, Proceedings of an international workshop (TU Berlin, Germany, September 1994), ed. Günter Hommel, Kluwer Academic Publishers, Dordrecht, 1995, 123–136 | DOI | Zbl

[60] R. Zijal, Analysis of discrete time deterministic and stochastic Petri nets, Ph.D. thesis, Technical University of Berlin, Germany, 1997

[61] R. Zijal, G. Ciardo, Discrete deterministic and stochastic Petri nets, ICASE Report, No 96–72, Institute for Computer Applications in Science and Engineering (ICASE), NASA, Langley Research Centre, Hampton, VA, USA, 1996, 23 pp.

[62] R. Zijal, G. Ciardo, G. Hommel, “Discrete deterministic and stochastic Petri nets”, Proc. $9^{th}$ ITG/GI Professional Meeting on Measuring, Modeling and Evaluation of Computer and Communication Systems (MMB) 1997, eds. K. Irmscher etc., 103–117, Berlin, 1997

[63] R. Zijal, R. German, “A new approach to discrete time stochastic Petri nets”, Proc. $11^{th}$ Int. Conf. on Analysis and Optimization of Systems, Discrete Event Systems (DES) 1994 (Sophia-Antipolis, France, 1994), Lecture Notes in Control and Information Sciences, 199, eds. G. Cohen, J.-P. Quadrat, 1994, 198–204 | DOI

[64] A. Zimmermann, “Modeling and evaluation of stochastic Petri nets with TimeNET 4.1”, Proc. $6^{th}$ Int. ICST Conf. on Performance Evaluation Methodologies and Tools (VALUETOOLS) (Cargèse, France, October 2012), eds. B. Gaujal, A. Jean-Marie, E. Jorswieck, A. Seuret, IEEE Computer Society Press, 2012, 1–10

[65] A. Zimmermann, J. Freiheit, R. German, G. Hommel, “Petri net modelling and performability evaluation with TimeNET 3.0”, Lect. Notes Comput. Sci., 1786, Springer, Berlin, 2000, 188–202 | DOI | Zbl

[66] A. Zimmermann, J. Freiheit, G. Hommel, “Discrete time stochastic Petri nets for modeling and evaluation of real-time systems”, Proc. $9^{th}$ Int. Workshop on Parallel and Distributed Real Time Systems (WPDRTS) (2001, San Francisco, USA), 2001, 282–286