License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2017.31
URN: urn:nbn:de:0030-drops-77957
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7795/
Go to the corresponding LIPIcs Volume Portal

Bouyer, Patricia ; Haddad, Serge ; Jugé, Vincent

Unbounded Product-Form Petri Nets

pdf-format:
LIPIcs-CONCUR-2017-31.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{bouyer_et_al:LIPIcs:2017:7795,
  author =	{Patricia Bouyer and Serge Haddad and Vincent Jug{\'e}},
  title =	{{Unbounded Product-Form Petri Nets}},
  booktitle =	{28th International Conference on Concurrency Theory (CONCUR 2017)},
  pages =	{31:1--31:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-048-4},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{85},
  editor =	{Roland Meyer and Uwe Nestmann},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7795},
  URN =		{urn:nbn:de:0030-drops-77957},
  doi =		{10.4230/LIPIcs.CONCUR.2017.31},
  annote =	{Keywords: Performance evaluation, infinite-state systems, Petri nets,  steady-state distribution}
}

Keywords: Performance evaluation, infinite-state systems, Petri nets, steady-state distribution
Collection: 28th International Conference on Concurrency Theory (CONCUR 2017)
Issue Date: 2017
Date of publication: 01.09.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI