Deficiency Zero Petri Nets and Product Form

• Autorzy: Mairesse J. , Nguyen H-T.
• Języki publikacji: EN

Abstrakty

EN

Consider a Markovian Petri net with race policy. The marking process has a "product form" stationary distribution if the probability of viewing a given marking can be decomposed as the product over places of terms depending only on the local marking. First we observe that the Deficiency Zero Theorem of Feinberg, developed for chemical reaction networks, provides a structural and simple sufficient condition for the existence of a product form. In view of this, we study the classical subclass of free-choice nets. Roughly, we show that the only Petri nets of this class which have a product form are the state machines, which can alternatively be viewed as Jackson networks.

Słowa kluczowe

EN

Petri net; Markovian Petri nets; Non-linear traffic equations; Kelly's theorem

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 105, nr 3
• Strony: 237--261
• Opis fizyczny: Bibliogr. 24 poz., wykr.

Twórcy

autor

Mairesse J.

autor

Nguyen H-T.

• LIAFA, Université Paris Diderot - Paris 7, 75205 Paris Cedex 13, France,

Bibliografia

• [1] M. Ajmone-Marsan, G. Balbo, A. Bobbio, G. Chiola, G. Conte, and A. Cumani. The effect of execution policies on the semantics and analysis of stochastic Petri nets. IEEE Trans. on Software Engin., 15(7):832-846, 1989.
• [2] D. Anderson, G. Craciun, and T. Kurtz. Product-form stationary distributions for deficiency zero chemical reaction networks. Bulletin of Mathematical Biology, 72:1947 - 1970, 2010.
• [3] D. Angeli, P. De Leenheer, and E. D. Sontag. A Petri net approach to the study of persistence in chemical reaction networks. Mathematical Biosciences, 210(2):598 - 618, 2007.
• [4] F. Baccelli, G. Cohen, G.J. Olsder, and J.P. Quadrat. Synchronization and Linearity. John Wiley & Sons, New York, 1992.
• [5] R. Boucherie and M. Sereno. On closed support T-invariants and the traffic equations. J. Appl. Probab., 35(2):473-481, 1998.
• [6] J. L. Coleman, W. Henderson, and P. G. Taylor. Product form equilibrium distributions and a convolution algorithm for stochastic Petri nets. Performance Evaluation, 26(3):159 - 180, 1996.
• [7] J. Desel. Basic linear algebraic techniques for place or transition nets. In Lectures on Petri Nets I, number 1491 in LNCS, pages 257-308. Springer-Verlag, 1996.
• [8] J. Desel and J. Esparza. Free Choice Petri Nets, volume 40 of Cambridge Tracts Theoret. Comput. Sci. Cambridge Univ. Press, 1995.
• [9] N. M. Van Dijk. Queueing Networks and Product Forms: A Systems Approach. John Wiley & Sons, 1993.
• [10] S. Donatelli and M. Sereno. On the product form solution for stochastic Petri nets. In 13-th Int. Conf. On Application and Theory of Petri Nets, volume 616 of LNCS, pages 154-172, 1992.
• [11] M. Feinberg. Lectures on chemical reaction networks. Lectures given at the Mathematics Research Center, University of Wisconsin, 1979. Available online on the web page: http://www.che.eng.ohio-state.edu/∼feinberg/LecturesOnReactionNetworks
• [12] G. Florin and S. Natkin. Generalization of queueing network product form solutions to stochastic Petri nets. IEEE Trans. Software Engrg., 17(2):99-107, 1991.
• [13] W. Gordon and G. Newell. Closed queuing systems with exponential servers. Oper. Res., 15:254-265, 1967.
• [14] S. Haddad, P. Moreaux, M. Sereno, and M. Silva. Product-form and stochastic Petri nets: a structural approach. Performance Evaluation, 59(4):313 - 336, 2005.
• [15] W. Henderson, D. Lucic, and P. Taylor. A net level performance analysis of stochastic Petri nets. J. Austral. Math. Soc. Ser. B, 31(2):176-187, 1989.
• [16] J.R. Jackson. Networks of waiting lines. Oper. Res., 5:518-521, 1957.
• [17] F. Kelly. Reversibility and Stochastic Networks. Wiley, New-York, 1979.
• [18] T. G. Kurtz. The relationship between stochastic and deterministic models for chemical reactions. Journal of Chemical Physics, 57(7):2976-2978, 1972.
• [19] A. A. Lazar and T. G. Robertazzi. Markovian Petri net protocols with product form solution. Performance Evaluation, 12(1):67 - 77, 1991.
• [20] J. Mairesse and H.-T. Nguyen. Deficiency zero Petri nets and product form. In G. Franceschinis and K.Wolf, editors, Petri Nets 2009, volume 5606 of LNCS, pages 103-122. Springer-Verlag, 2009.
• [21] T. Murata. Petri nets: Properties, analysis and applications. Proceedings of the IEEE, 77(4):541 - 580, 1989.
• [22] C.A. Petri and W. Reisig. Petri net. Scholarpedia, 3(4):6477, 2008.
• [23] C. Reutenauer. The mathematics of Petri nets. Prentice Hall, 1990.
• [24] R. Serfozo. Introduction to stochastic networks, volume 44 of Applications of Mathematics. Springer-Verlag, New York, 1999.