DISCRETE DETERMINISTIC AND STOCHASTIC PETRI NETS
Robert Zijal, Gianfranco Ciardo, Günter Hommel · 1996
Petri nets augmented with timing specifications gained a wide acceptance in the area of performance and reliability evaluation of complex systems exhibiting concurrency, synchronization, and conicts. The state space of time-extended Petri nets is mapped onto its basic underlying stochastic process, which can be shown to be Markovian under the assumption of exponentially distributed ring times. The integration of exponentially and non-exponentially distributed timing is still one of the major problems for the analysis and was first attacked for continuous-time Petri nets at the cost of structural or analytical restrictions. We propose a discrete deterministic and stochastic Petri net (DDSPN) formalism with no imposed structural or analytical restrictions where transitions can fire either in zero time or according to arbitrary ring times that can be represented as the time to absorption in a finite absorbing discrete-time Markov chain (DTMC). Exponentially distributed ring times are then approximated arbitrarily well by geometric distributions. Deterministic ring times are a special case of the geometric distribution. The underlying stochastic process of a DDSPN is then also a DTMC, from which the transient and stationary solution can be obtained by standard techniques. A comprehensive algorithm and some state space reduction techniques for the analysis of DDSPNs are presented, including the automatic detection of conicts and confusions, which removes a major obstacle for the analysis of discrete-time models.