Document Open Access Logo

Unbounded Product-Form Petri Nets

Authors Patricia Bouyer, Serge Haddad, Vincent Jugé

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2017.31.pdf
  • Filesize: 0.57 MB
  • 16 pages

Document Identifiers

Author Details

Patricia Bouyer
Serge Haddad
Vincent Jugé

Cite As Get BibTex

Patricia Bouyer, Serge Haddad, and Vincent Jugé. Unbounded Product-Form Petri Nets. In 28th International Conference on Concurrency Theory (CONCUR 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 85, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.CONCUR.2017.31

Abstract

Computing steady-state distributions in infinite-state stochastic systems is in general a very difficult task. Product-form Petri nets are those Petri nets for which the steady-state distribution can be described as a natural product corresponding, up to a normalising constant, to an exponentiation of the markings. However, even though some classes of nets are known to have a product-form distribution, computing the normalising constant can be hard. The class of (closed) \Pi^3-nets has been proposed in an earlier work, for which it is shown that one can compute the steady-state distribution efficiently. However these nets are bounded. In this paper, we generalise queuing Markovian networks and closed \Pi^3-nets to obtain the class of open \Pi^3-nets, that generate infinite-state systems. We show interesting properties of these nets: (1) we prove that liveness can be decided in polynomial time, and that reachability in live \Pi^3-nets can be decided in polynomial time; (2) we show that we can decide ergodicity of such nets in polynomial time as well; (3) we provide a pseudo-polynomial time algorithm to compute the normalising constant.

Subject Classification

Keywords
  • Performance evaluation
  • infinite-state systems
  • Petri nets
  • steady-state distribution

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Parosh Aziz Abdulla, Noomene Ben Henda, Richard Mayr, and Sven Sandberg. Limiting behavior of markov chains with eager attractors. In Proc. 3rd International Conference on the Quantitative Evaluation of Systems (QEST'06), pages 253-264, 2006. Google Scholar
  2. Simonetta Balsamo and Andrea Marin. Determining product-form steady-state solutions of generalized stochastic Petri nets by the analysis of the reversed process. In Proc. 7th IEEE/ACS International Conference on Computer Systems and Applications (AICCSA'09), pages 808-815. IEEE Computer Society, 2009. Google Scholar
  3. Simonetta Balsamo and Andrea Marin. Performance engineering with product-form models: efficient solutions and applications. In Proc. 2nd Joint WOSP/SIPEW International Conference on Performance Engineering (ICPE'11), pages 437-448. ACM Press, 2011. Google Scholar
  4. E. Cardoza, Richard J. Lipton, and Albert R. Meyer. Exponential space complete problems for Petri nets and commutative semigroups: Preliminary report. In Proc. 8th Annual ACM Symposium on Theory of Computing (STOC'76), pages 50-54. ACM Press, 1976. Google Scholar
  5. E. Cinlar. Introduction to Stochastic Processes. Prentice Hall, 1975. Google Scholar
  6. J. L. Coleman, William Henderson, and Peter G. Taylor. Product form equilibrium distributions and a convolution algorithm for stochastic Petri nets. Performance Evaluation, 26(3):159-180, 1996. Google Scholar
  7. Javier Esparza and Mogens Nielsen. Decidability issues for Petri nets - A survey. Bulletin of the EATCS, 52:244-262, 1994. Google Scholar
  8. Gerard Florin and Stéphane Natkin. One-place unbounded stochastic Petri nets: Ergodic criteria and steady-state solutions. Journal of Systems and Software, 6(1):103 - 115, 1986. Google Scholar
  9. William J. Gordon and Gordon F. Newell. Closed queuing systems with exponential servers. Operations Research, 15(2):254-265, 1967. Google Scholar
  10. Serge Haddad, Jean Mairesse, and Hoang-Thach Nguyen. Synthesis and analysis of product-form Petri nets. Fundamenta Informaticae, 122(1-2):147-172, 2013. Google Scholar
  11. Serge Haddad, Patrice Moreaux, Matteo Sereno, and Manuel Silva. Product-form and stochastic Petri nets: A structural approach. Performance Evaluation, 59(4):313-336, 2005. Google Scholar
  12. Peter G. Harrison and Catalina M. Lladó. Hierarchically constructed Petri-nets and product-forms. In Proc. 5th International ICST Conference on Performance Evaluation Methodologies and Tools Communications (VALUETOOLS'11), pages 101-110. ICST/ACM Press, 2011. Google Scholar
  13. James R. Jackson. Jobshop-like queueing systems. Management Science, 10(1):131-142, 1963. Google Scholar
  14. Matthias Jantzen. Complexity of place/transition nets. In Proc. Advances in Petri Nets (1986), volume 254 of Lecture Notes in Computer Science, pages 413-434. Springer, 1987. Google Scholar
  15. Aurel A. Lazar and Thomas G. Robertazzi. Markovian Petri net protocols with product form solution. Performance Evaluation, 12(1):67 - 77, 1991. Google Scholar
  16. Man Li and Nicolas D.Georganas. Exact parametric analysis of stochastic Petri nets. IEEE Transactions on Computers, 41:1176-1180, 1992. Google Scholar
  17. Jean Mairesse and Hoang-Thach Nguyen. Deficiency zero Petri nets and product form. Fundamenta Informaticae, 105(3):237-261, 2010. Google Scholar
  18. Andrea Marin, Simonetta Balsamo, and Peter G. Harrison. Analysis of stochastic Petri nets with signals. Performance Evaluation, 69(11):551-572, 2012. Google Scholar
  19. Marco Ajmone Marsan, Gianfranco Balbo, Gianni Conte, Susanna Donatelli, and Giuliana Franceschinis. Modelling with Generalized Stochastic Petri Nets. John Wiley &Sons, Inc., 1995. Google Scholar
  20. Michael K. Molloy. Performance analysis using stochastic Petri nets. IEEE Transactions on Computers, 31(9):913-927, 1982. Google Scholar
  21. J.L. Peterson. Petri Net Theory and the Modeling of Systems. Prentice Hall, 1981. Google Scholar
  22. Charles Rackoff. The covering and boundedness problems for vector addition systems. Theoretical Computer Science, 6:223-231, 1978. Google Scholar
  23. Matteo Sereno and Gianfranco Balbo. Mean value analysis of stochastic Petri nets. Performance Evaluation, 29(1):35-62, 1997. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact