Tag Archives: Stochastic Petri Nets

14/02/2017 – Talk by Ivan Stojic

Title: Algorithms for stationary analysis of stochastic Petri nets
Time: 12:30
Location: Meeting room, Building Zeta
Type: Research Result
Speaker: Ivan Stojic
Abstract:
Stochastic Petri nets (SPN) are a Markovian formalism for qualitative and quantitative analysis of discrete event dynamic systems. Among other uses, they have been used extensively in performance evaluation of telecommunication systems, computer systems and networks. Analysis of steady-state behaviour of an SPN model usually requires stationary analysis of a continuous-time Markov chain (CTMC) underlying the SPN, whose state space for many practical models is too large to be analysed by direct methods. This serious drawback is shared with many other modeling formalisms and is usually referred to as state space explosion. Usually simulation can be employed to analyse such models. An alternative is to restrict the SPN formalism to product-form SPNs, a class of nets whose unnormalised stationary probability distribution can be obtained in closed form, making stationary analysis much simpler. In this thesis we present algorithms for stationary analysis of SPN models based on efficient encoding of state spaces and transition functions by multi-valued decision diagrams, an efficient data structure. After a short introduction to SPNs and their steady-state analysis, we start with simulation of SPNs and present an algorithm for perfect sampling of SPNs that can be used to directly obtain samples from the stationary distribution. After this, we turn to product-form SPNs and present an algorithm for computation of normalising constant, needed for the normalisation of stationary probabilities in the analysis of product-form models.

21/10/2015: Talk by Ivan Stojic

Title: Perfect sampling in stochastic Petri nets using decision diagrams
Time: 13:00
Location: Meeting Room, building Zeta
Type: Research result
Speaker: Ivan Stojic
Abstract: Stochastic Petri nets (SPN) 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 (CTMC). Since solving a CTMC underlying an SPN is often computationally too expensive due to state space explosion, simulation and sampling techniques are often used in analysis of SPN models. In this talk we present an algorithm for generating samples from stationary probability distribution of the CTMC underlying an SPN. The algorithm uses uniformization and decision diagrams to exploit regularities in structure of CTMCs obtained from SPNs in order to efficiently implement coupling from the past, a well known algorithm for perfect sampling.