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.