Synthesis and Analysis of Product-form Petri Nets

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

Abstrakty

EN

For a large Markovian model, a "product form" is an explicit description of the steadystate behaviour which is otherwise generally untractable. Being first introduced in queueing networks, it has been adapted to Markovian Petri nets. Here we address three relevant issues for product-form Petri nets which were left fully or partially open: (1) we provide a sound and complete set of rules for the synthesis; (2) we characterise the exact complexity of classical problems like reachability; (3) we introduce a new subclass for which the normalising constant (a crucial value for product-form expression) can be efficiently computed.

Słowa kluczowe

EN

Petri nets; product-form; synthesis; complexity analysis; reachability; normalising constant

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 122, nr 1-2
• Strony: 147--172
• Opis fizyczny: Bibliogr. 25 poz., rys.

Twórcy

autor

Haddad S.

• LSV, CNRS UMR 8643, INRIA ENS Cachan, Cachan, France

autor

Mairesse J.

• LIAFA, CNRS UMR 7089 Universit´e Paris 7, Paris, France

autor

Nguyen H. T.

• LIAFA, CNRS UMR 7089 Universit´e Paris 7, Paris, France

Bibliografia

• [1] M. AjmoneMarsan, G. Balbo, G. Conte, S. Donatelli, G. Franceschinis. Modelling with Generalized Stochastic Petri Nets. Wiley, 1995.
• [2] F. Baccelli, G. Cohen, G.J. Olsder, and J.P. Quadrat. Synchronization and Linearity. Wiley, 1992.
• [3] S. Balsamo, P. G. Harrison and A. Marin. Methodological construction of product-form stochastic Petri nets for performance evaluation Journal of Systems and Software, 85(7):1520–1539, 2012.
• [4] S. Balsamo and A. Marin. Performance engineering with product-form models: efficient solutions and applications Proceedings of the second joint WOSP/SIPEW international conference on Performance engineering (ICPE’11), ACM publisher: 437–448, Karlsruhe, Germany, 2011.
• [5] S. Balsamo, A.Marin. Composition of product-form Generalized Stochastic Petri Nets: a modular approach. Proc. ESM 2009, Eurosis 23rd European Simulation and Modelling Conference, Leicester, United-Kingdom, 2009.
• [6] F. Baskett, K. M. Chandy, R. R. Muntz, F. Palacios. Open, closed and mixed networks of queues with different classes of customers. Journal of the ACM, 22(2):248–260, 1975.
• [7] R. J. Boucherie, M. Sereno. On closed support T-invariants and traffic equations. Journal of Applied Probability, (35):473–481, 1998.
• [8] G. Chiola, G. Franceschinis, R. Gaeta, M. Ribaudo. Great SPN 1.7: Graphical Editor and Analyzer for Timed and Stochastic Petri Nets. Performance Evaluation 24(1-2):47–68, 1995.
• [9] J. Desel and J. Esparza Free Choice Petri Nets, volume 40 of Cambridge Tracts Theoret. Comput. Sci. Cambridge Univ. Press, 1995.
• [10] J. Esparza and M. Nielsen. Decidability issues for Petri nets - a survey. Journal of Informatik Processing and Cybernetics, 30(3):143–160, 1994.
• [11] J.L. Coleman,W. Henderson, P.G. Taylor. Product form equilibrium distributions and a convolution algorithm for stochastic Petri nets. Performance Evaluation, 26(3):159–180, 1996.
• [12] J. Esparza. Reduction and Synthesis of Live and Bounded Free Choice Petri Nets. Information and Computation, 114(1):50–87, 1994.
• [13] M. Feinberg. Lectures on chemical reaction networks. Math. Research Center, Univ. Wisconsin, 1979. Available online at http://www.che.eng.ohio-state.edu/_feinberg/LecturesOnReactionNetworks.
• [14] S. Haddad, P. Moreaux, M. Sereno, M. Silva Product-form and stochastic Petri nets: a structural approach. Performance Evaluation, 59:313–336, 2005.
• [15] S. Haddad, J. Mairesse, H.-T. Nguyen Synthesis and analysis of product-form Petri nets. Petri Nets 2011, LNCS 6709: 288–307, 2011.
• [16] P. G. Harrison and L. M. Catalina Hierarchically constructed Petri-nets and product-forms. Proceedings of the 5th International ICST Conference on Performance Evaluation Methodologies and Tools (VALUETOOLS’ 11), ICST: 101–110, Paris, France, 2011.
• [17] W. Henderson, D. Lucic, P.G. Taylor. A net level performance analysis of stochastic Petri nets. Journal of Australian Mathematical Soc. Ser. B, 31:176–187, 1989.
• [18] J. R. Jackson. Jobshop-like Queueing Systems. Management Science, 10(1):131–142, 1963.
• [19] F. Kelly. Reversibility and Stochastic Networks. Wiley, 1979.
• [20] A. A. Lazar, T. G. Robertazzi. Markovian Petri Net Protocols with Product Form Solution. Proc. of INFOCOM 87: 1054–1062, San Francisco, USA, 1987.
• [21] M. Li, N. D. Georganas. Parametric Analysis of Stochastic Petri Nets, Fifth International Conference on Modelling and Tools for Computer Performance Evaluation, Torino, Italy, 1991,
• [22] J. Mairesse, H-T. Nguyen. Deficiency Zero Petri Nets and Product Form. Fundamenta Informaticae, 105(3): 237–261, 2010.
• [23] E. Mayr, A. Meyer. The complexity of the word problem for commutative semigroups an polynomial ideals. Advances in Math, 46:305–329, 1982.
• [24] C. Papadimitriou. Computational Complexity. Addison Wesley, 1994.
• [25] M. Reiser, S.S. Lavenberg. Mean Value Analysis of Closed Multichain Queueing Networks. Journal of the ACM, 27(2):313–322, 1980.