# zbMATH — the first resource for mathematics

Turning back time in Markovian process algebra. (English) Zbl 1044.68117
Summary: Product-form solutions in Markovian Process Algebra (MPA) are constructed using properties of reversed processes. The compositionality of MPAs is directly exploited, allowing a large class of hierarchically constructed systems to be solved for their state probabilities at equilibrium. The paper contains new results on both reversed stationary Markov processes as well as MPA itself and includes a mechanisable proof in MPA notation of Jackson’s theorem for product-form queueing networks. Several examples are used to illustrate the approach.

##### MSC:
 68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
##### Keywords:
product-form queueing networks
##### Software:
 [1] V.V. Anisimov, Asymptotic aggregation of states for finite Markov processes, unpublished private communication, 2001. [2] Bernardo, M.; Gorrieri, R., A tutorial on empaa theory of concurrent processes with nondeterminism, priorities, probabilities and time, Theoret. comput. sci., 202, 1-54, (1998) · Zbl 0902.68075 [3] Burke, P.J., The output of a queueing system, Oper. res., 4, 699-704, (1956) · Zbl 1414.90097 [4] G. Clark, J. Hillston, Product form solution for an insensitive stochastic process algebra structure, Performance Evaluat. (2002) to appear. · Zbl 1159.68514 [5] Gelenbe, E., Random neural networks with positive and negative signals and product form solution, Neural comput., 1, 4, 502-510, (1989) [6] Gelenbe, E., Queueing networks with negative and positive customers, J. appl. probab., 28, 656-663, (1991) · Zbl 0741.60091 [7] Goetz, N.; Herzog, U.; Rettelbach, M., Multiprocessor and distributed system designthe integration of functional specification and performance analysis using stochastic process algebras, (), 121-146 [8] Harrison, P.G.; Hillston, J., Exploiting quasi-reversible structures in Markovian process algebra models, Comput. J., 38, 7, 510-520, (1995) [9] Harrison, P.G.; Patel, N.M., Performance modelling of communication networks and computer architectures, (1992), Addison-Wesley Reading, MA [10] Harrison, P.G.; Strulo, B., Spades – a process algebra for discrete event simulation, J. logic comput., 10, 1, 3-42, (2000) · Zbl 0949.68112 [11] J. Hillston, A compositional approach to performance modelling, Ph.D. Thesis, University of Edinburgh, 1994. · Zbl 1080.68003 [12] Hillston, J.; Thomas, N., Product form solution for a class of PEPA models, Performance evaluat., 35, 3-4, 171-192, (1999) · Zbl 1052.68638 [13] Jackson, J.R., Jobshop-like queueing systems, Manag. sci., 10, 1, 131-142, (1963) [14] Katoen, J.P., Markovian bisimulation, Sci. comput. programming, 202, 1-54, (2000) [15] J.P. Katoen P. D’Argenio, E. Brinksma, General purpose discrete event simulation using $$♠$$, in: Proc. PAPM 1998, Nice, July 1998, pp. 85-102. [16] Kelly, F.P., Reversibility and stochastic networks, (1979), Wiley New York · Zbl 0422.60001 [17] Knottenbelt, W.; Harrison, P.; Mestern, M.; Kritzinger, P., A probabilistic dynamic technique for the distributed generation of very large state spaces, Performance evaluat. J., 39, 1-4, 127-148, (2000) · Zbl 1052.68556 [18] W. Knottenbelt, P. Harrison. Distributed disk-based solution techniques for large Markov models, in: Proc. 3rd Internat. Conf. Numerical Solution of Markov Chains, NSMC ’99, Zaragoza, September 1999, pp. 58-75. [19] Plateau, B.; Stewart, W., Kronecker algebra, J. assoc. comput. Mach., 45, 2, (1998) [20] Sereno, M., Towards a product form solution for stochastic process algebras, Comput. J., 38, 7, 622-632, (1995)