Perfect simulation of stochastic automata networks

Paulo Fernandes, Jean Marc Vincent, Thais Webber*

*Corresponding author for this work

Research output: Chapter in Book/Published conference outputConference publication


The solution of continuous and discrete-time Markovian models is still challenging mainly when we model large complex systems, for example, to obtain performance indexes of parallel and distributed systems. However, iterative numerical algorithms, even well-fitted to a multidimensional structured representation of Markov chains, still face the state space explosion problem. Discrete-event simulations can estimate the stationary distribution based on long run trajectories and are also alternative methods to estimate performance indexes of models. Perfect simulation algorithms directly build steady-state samples avoiding the warm-up period and the initial state bias of forward simulations. This paper introduces the concepts of backward coupling and the advantages of monotonicity properties and component-wise characteristics to simulate Stochastic Automata Networks (SAN). The main contribution is a novel technique to solve SAN descriptions originally unsolvable by iterative methods due to large state spaces. This method is extremely efficient when the state space is large and the model has dynamic monotonicity because it is possible to contract the reachable state space in a smaller set of maximal states. Component-wise characteristics also contribute to the state space reduction extracting extremal states of the model underlying chain. The efficiency of this technique applied to sample generation using perfect simulation is compared to the overall efficiency of using an iterative numerical method to predict performance indexes of SAN models.

Original languageEnglish
Title of host publicationAnalytical and Stochastic Modeling Techniques and Applications - 15th International Conference, ASMTA 2008, Proceedings
Number of pages15
Publication statusPublished - 26 May 2008
Event15th International Conference on Analytical and Stochastic Modeling Techniques and Applications, ASMTA 2008 - Nicosia, Cyprus
Duration: 4 Jun 20086 Jun 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5055 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference15th International Conference on Analytical and Stochastic Modeling Techniques and Applications, ASMTA 2008


Dive into the research topics of 'Perfect simulation of stochastic automata networks'. Together they form a unique fingerprint.

Cite this