Geodesic
Stochastic process reduction for performance evaluation in dtsiPBC
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 12 (2015), pp. 513-551.

Voir la notice de l'article provenant de la source Math-Net.Ru

Petri box calculus (PBC) is a well-known algebra of concurrent processes with a Petri net semantics. In the paper, we consider an extension of PBC with discrete stochastic time and immediate multiactions, which is referred to as discrete time stochastic and immediate PBC (dtsiPBC). Performance analysis methods for concurrent and distributed systems with random time delays are investigated in the framework of the new stochastic process algebra. It is demonstrated that the performance evaluation is possible not only via the underlying semi-Markov chains of the algebraic process expressions but also by exploring the reduced discrete time Markov chains, obtained from the semi-Markov chains by eliminating their states with zero residence time (called vanishing states). The latter approach simplifies performance analysis of large systems due to abstraction from many instantaneous activities, such as those used to specify logical conditions, probabilistic branching, as well as urgent or internal (unobservable) work.
Keywords: stochastic process algebras, stochastic Petri nets, Petri box calculus, discrete time, immediate multiactions, operational semantics, transition systems, performance analysis, vanishing states, reduction.
Mots-clés : Markov chains 
@article{SEMR_2015_12_a55,
     author = {I. V. Tarasyuk and H. Maci\`a and V. Valero},
     title = {Stochastic process reduction for performance evaluation in {dtsiPBC}},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {513--551},
     publisher = {mathdoc},
     volume = {12},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2015_12_a55/}
}
TY  - JOUR
AU  - I. V. Tarasyuk
AU  - H. Macià
AU  - V. Valero
TI  - Stochastic process reduction for performance evaluation in dtsiPBC
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2015
SP  - 513
EP  - 551
VL  - 12
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2015_12_a55/
LA  - en
ID  - SEMR_2015_12_a55
ER  - 
%0 Journal Article
%A I. V. Tarasyuk
%A H. Macià
%A V. Valero
%T Stochastic process reduction for performance evaluation in dtsiPBC
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2015
%P 513-551
%V 12
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2015_12_a55/
%G en
%F SEMR_2015_12_a55
I. V. Tarasyuk; H. Macià; V. Valero. Stochastic process reduction for performance evaluation in dtsiPBC. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 12 (2015), pp. 513-551. http://geodesic.mathdoc.fr/item/SEMR_2015_12_a55/

[1] Balbo G., “Introduction to generalized stochastic Petri nets”, Lecture Notes in Computer Science, 4486, 2007, 83–131 | DOI | Zbl

[2] Bernardo M., Bravetti M., Reward based congruences: can we aggregate more?, Lecture Notes in Computer Science, 2165, 2001, 136–151 http://www.cs.unibo.it/b̃ravetti/papers/papm01b.ps | DOI | MR | Zbl

[3] Bernardo M., Gorrieri R., “A tutorial on EMPA: a theory of concurrent processes with nondeterminism, priorities, probabilities and time”, Theoretical Computer Science, 202 (1998), 1–54 http://www.sti.uniurb.it/bernardo/documents/tcs202.pdf | DOI | MR | Zbl

[4] Best E., Devillers R., Hall J. G., “The box calculus: a new causal algebra with multi-label communication”, Lecture Notes in Computer Science, 609, 1969, 21–69 | DOI | MR

[5] Best E., Devillers R., Koutny M., Petri net algebra, EATCS Monographs on Theoretical Computer Science, Springer Verlag, 2001 | DOI | MR

[6] Best E., Koutny M., “A refined view of the box algebra”, Lecture Notes in Computer Science, 935, 1995, 1–20 http://parsys.informatik.uni-oldenburg.de/b̃est/publications/pn95.ps.gz | DOI | MR

[7] Bradley J. T., “Semi-Markov PEPA: modelling with generally distributed actions”, International Journal of Simulation, 6:3–4 (2005), 43–51 http://pubs.doc.ic.ac.uk/semi-markov-pepa/semi-markov-pepa.pdf

[8] Ciardo G., Muppala J. K., Trivedi K. S., “On the solution of GSPN reward models”, Performance Evaluation, 12:4 (1991), 237–253 http://people.ee.duke.edu/k̃st/spn_papers/gspnrew.ps | DOI | Zbl

[9] Haverkort B. R., “Markovian models for performance and dependability evaluation”, Lecture Notes in Computer Science, 2090, 2001, 38–83 http://www-i2.informatik.rwth-aachen.de/Teaching/Seminar/VOSS2005/have01.pdf | DOI | Zbl

[10] Hermanns H., Rettelbach M., “Syntax, semantics, equivalences and axioms for MTIPP”, Proceedings of $2^{nd}$ Workshop on Process Algebras and Performance Modelling (University of Erlangen, Germany, 1994), Arbeitsberichte des IMMD, 27, eds. Herzog U., Rettelbach M., Regensberg–Erlangen, 71–88 http://ftp.informatik.uni-erlangen.de/local/inf7/papers/Hermanns/syntax_semantics_equivalences_axioms_for_MTIPP.ps.gz

[11] Hillston J., A compositional approach to performance modelling, Cambridge University Press, UK, 1996 http://www.dcs.ed.ac.uk/pepa/book.pdf | MR

[12] Katoen J.-P., 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, 303 pp.

[13] Kulkarni V. G., Modeling and analysis of stochastic systems, Texts in Statistical Science, Chapman and Hall/CRC Press, 2009 | MR

[14] Macià H., Valero V., Cazorla D., Cuartero F., “Introducing the iteration in sPBC”, Lecture Notes in Computer Science, 3235, 2004, 292–308 http://www.info-ab.uclm.es/retics/publications/2004/forte04.pdf | DOI | Zbl

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

[16] Macià H., Valero V., de Frutos D., “sPBC: a Markovian extension of finite Petri box calculus”, Proceedings of $9^{th}$ IEEE International Workshop PNPM'01 (Aachen, Germany, 2001), IEEE Computer Society Press, 207–216 http://www.info-ab.uclm.es/retics/publications/2001/pnpm01.ps

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

[18] Marsan M. A., “Stochastic Petri nets: an elementary introduction”, Lecture Notes in Computer Science, 424, 1990, 1–29 | DOI | MR

[19] Marsan M. A., Balbo G., Conte G., Donatelli S., Franceschinis G., Modelling with generalized stochastic Petri nets, Wiley Series in Parallel Computing, John Wiley and Sons, 1995 http://www.di.unito.it/g̃reatspn/GSPN-Wiley | Zbl

[20] Milner R. A. J., Communication and concurrency, Prentice-Hall, Upper Saddle River, NJ, USA, 1989 | Zbl

[21] Molloy M. K., “Discrete time stochastic Petri nets”, IEEE Transactions on Software Engineering, 11:4 (1985), 417–423 | DOI | MR | Zbl

[22] Mudge T. N., Al-Sadoun H. B., “A semi-Markov model for the performance of multiple-bus systems”, IEEE Transactions on Computers, C-34:10 (1985), 934–942 http://www.eecs.umich.edu/t̃nm/papers/SemiMarkov.pdf | DOI

[23] Ross S. M., Stochastic processes, $2^{nd}$ edition, John Wiley and Sons, New York, USA, 1996 | MR | Zbl

[24] Tarasyuk I. V., Discrete time stochastic Petri box calculus, Berichte aus dem Department für Informatik, 3/05, Carl von Ossietzky Universität Oldenburg, Germany, 2005 http://itar.iis.nsk.su/files/itar/pages/dtspbcib_cov.pdf

[25] Tarasyuk I. V., “Iteration in discrete time stochastic Petri box calculus”, Bulletin of the Novosibirsk Computing Center, Series Computer Science, 24, IIS Special Issue (2005) http://itar.iis.nsk.su/files/itar/pages/dtspbcfi.pdf

[26] Tarasyuk I. V., “Stochastic Petri box calculus with discrete time”, Fundamenta Informaticae, 76:1–2 (2007) http://itar.iis.nsk.su/files/itar/pages/dtspbcfi.pdf | MR | Zbl

[27] Tarasyuk I. V., “Equivalence relations for modular performance evaluation in dtsPBC”, Mathematical Structures in Computer Science, 24:1 (2014), 78–154 http://itar.iis.nsk.su/files/itar/pages/dtsdphms.pdf | MR

[28] Tarasyuk I. V., Macià H., Valero V., Discrete time stochastic Petri box calculus with immediate multiactions, Technical Report DIAB-10-03-1, Department of Computer Systems, High School of Computer Science Engineering, University of Castilla-La Mancha, Albacete, Spain, 2010 http://itar.iis.nsk.su/files/itar/pages/dtsipbc.pdf

[29] Tarasyuk I. V., Macià H., Valero V., “Discrete time stochastic Petri box calculus with immediate multiactions dtsiPBC”, Proc. $6^{th}$ International Workshop on Practical Applications of Stochastic Modelling - 12 (PASM'12) and $11^{th}$ International Workshop on Parallel and Distributed Methods in Verification - 12 (PDMC'12), Electronic Notes in Theoretical Computer Science, 296, 2013, 229–252 http://itar.iis.nsk.su/files/itar/pages/dtsipbcentcs.pdf | DOI

[30] Tarasyuk I. V., Macià H., Valero V., “Performance analysis of concurrent systems in algebra dtsiPBC”, Programming and Computer Software, 40:5 (2014), 229–249 | DOI | MR