Perfect Sampling in Stochastic Petri Nets Using Decision Diagrams

Stochastic Petri nets are an important formalism for performance evaluation of telecommunication systems and computer hardware and software architectures whose underlying process is a Continuous Time Markov Chain. In practice, performance evaluation based on Petri net models suffers the problem of state space explosion which makes exact analyses computationally prohibitive and hence practitioners usually resort to simulation. In this paper we propose an algorithm for perfect sampling in stochastic Petri nets whose transitions have single or infinite server semantics. Obtained samples are distributed according to stationary distribution of the net, allowing for running of stationary simulations without warm up period by starting a simulation run from an obtained sample. We implement coupling from the past - an algorithm for perfect sampling of discrete time Markov chains - to sample from the stationary probability distribution of the stochastic process underlying the Petri net. We study the performance of the algorithm under different scenarios.