Abstract
Petri box calculus PBC is a well-known algebra of concurrent processes with a Petri net semantics. In the paper, an extension of PBC with discrete stochastic time and immediate multiactions, which is referred to as discrete time stochastic and immediate PBC (dtsiPBC), is considered. 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 dtsiPBC expressions but also with the use of the underlying discrete time Markov chains, and the latter analysis technique is more optimal.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Hermanns, H. and Rettelbach, M., Syntax, semantics, equivalences and axioms for MTIPP, Proc. of the 2nd Workshop on Process Algebras and Performance Modelling (PAPM’94), Regensberg, 1994, pp. 71–88.
Hillston, J., A Compositional Approach to Performance Modelling, Cambridge (UK): Cambridge Univ. Press, UK, 1996.
Bernardo, M. and Gorrieri, R., A tutorial on EMPA: a theory of concurrent processes with nondeterminism, priorities, probabilities and time, Theor. Comput. Sci., 1998, vol. 202, pp. 1–54.
Best, E., Devillers, R., and Hall, J.G., The box calculus: a new causal algebra with multi-label communication, Lect. Notes Comp. Sci., 1992, vol. 609. pp. 21–69.
Best, E. and Koutny, M., A refined view of the box algebra, Lect. Notes Comp. Sci., 1995, vol. 935, pp. 1–20.
Best, E., Devillers, R., and Koutny, M., Petri Net Algebra, EATCS Monographs on Theoretical Comp. Sci., Springer, 2001.
Milner, R.A.J., Communication and Concurrency, Upper Saddle River, NJ: Prentice-Hall, 1989.
Macià, H., Valero, V., and de Frutos, D., sPBC: a Markovian extension of finite Petri box calculus, Proc. of the 9th IEEE Int. Workshop on Petri Nets and Performance Models (PNPM’01), Aachen: IEEE Comput. Society, 2001. pp. 207–216.
Macià, H., Valero, V., Cazorla, D., and Cuartero, F., Introducing the iteration in sPBC, Lect. Notes Comp. Sci., 2004, vol. 3235, pp. 292–308.
Macià, H., Valero, V., Cuartero, F., and Ruiz, M.C., sPBC: a Markovian extension of Petri box calculus with immediate multiactions, Fundamenta Informaticae, 2008, vol. 87, nos. 3–4, pp. 367–406.
Tarasyuk, I.V., Discrete time stochastic Petri box calculus. Oldenburg, Germany, 2005 (Berichte aus dem Department für Informatik. Carl von Ossietzky Univ. Oldenburg. no. 3/05).
Tarasyuk, I.V., Stochastic Petri box calculus with discrete time, Fundamenta Informaticae, 2007, vol. 76, nos. 1–2, pp. 189–218.
Tarasyuk, I.V., Iteration in discrete time stochastic Petri box calculus, Bulletin of the Novosibirsk Computing Center, Series Comp. Sci., IIS Special Issue, 2006, vol. 24, pp. 129–148.
Tarasyuk, I.V., Macià, H., and Valero, V., Discrete time stochastic Petri box calculus with immediate multi-actions, Technical Report, Department of Computer Systems, High School of Information Engineering, Univ. of Castilla-La Mancha. no. DIAB-10-03-1.
Tarasyuk, I.V., Macià, H., Valero, V., Discrete time stochastic Petri box calculus with immediate multiactions dtsiPBC, in Electronic Notes in Theoretical Computer Science, Elsevier, 2013, vol. 296, pp. 229–252.
Molloy, M.K., Discrete time stochastic Petri nets, IEEE Trans. Software Eng., 1985, vol. 11, no. 4. pp. 417–423.
Ross, S.M., Stochastic Processes, New York: Wiley, 1996.
Bernardo, M. and Bravetti, M., Reward based congruences: can we aggregate more?, Lect. Notes Comp. Sci., 2001, vol. 2165, pp. 136–151.
Balbo, G., Introduction to generalized stochastic Petri nets, Lect. Notes Comp. Sci., 2007, vol. 4486. pp. 83–131.
van Glabbeek, R.J., Smolka, S.A., and Steffen, B., Reactive, generative, and stratified models of probabilistic processes, Information Computation, 1995, vol. 121, no. 1, pp. 59–80.
Zimmermann, A., Freiheit, J., and Hommel, G., Discrete time stochastic Petri nets for modeling and evaluation of real-time systems, Proc. of the 9th Int. Workshop on Parallel and Distributed Real Time Systems (WPDRTS’01), San Francisco, 2001, pp. 282–286.
Zijal, R., Ciardo, G., and Hommel, G., Discrete deterministic and stochastic Petri nets, Proc. of the 9th ITG/GI Professional Meeting “Messung, Modellierung und Bewertung von Rechen- und Kommunikationssystemen”(MMB’97), VDE-Verlag, Berlin, 1997, pp. 103–117.
Buchholz P. and Tarasyuk, I.V., Net and algebraic approaches to probabilistic modeling, Joint Novosibirsk Computing Center and Institute of Informatics Systems Bulletin, Series Comp. Sci., Novosibirsk, 2001, vol. 15, pp. 31–64.
Haverkort, B.R., Markovian models for performance and dependability evaluation, Lect. Notes Comp. Sci., 2001, vol. 2090, pp. 38–83.
van Glabbeek, R.J., The linear time — branching time spectrum II: the semantics of sequential systems with silent moves (extended abstract), Lect. Notes Comp. Sci., 1993, vol. 715, pp. 66–81.
Mudge, T.N. and Al-Sadoun, H.B., A semi-Markov model for the performance of multiple-bus systems, IEEE Trans. Computers, 1985, vol. C-34, no. 10, pp. 934–942.
Katoen, J.-P., Quantitative and qualitative extensions of event structures, Ph. D. Thesis, Enschede, The Netherlands, 1996, (CTIT Ph. D.-thesis series. Centre for Telematics and Information Technology, University of Twente, no. 96-09).
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © I.V. Tarasyuk, H. Macià, V. Valero, 2014, published in Programmirovanie, 2014, Vol. 40, No. 5.
Rights and permissions
About this article
Cite this article
Tarasyuk, I.V., Macià, H. & Valero, V. Performance analysis of concurrent systems in algebra dtsiPBC. Program Comput Soft 40, 229–249 (2014). https://doi.org/10.1134/S0361768814050089
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S0361768814050089