Perfect Simulation of Stochastic Automata Networks. Fernandes, P., Vincent, J., & Webber, T. In Al-Begain, K., Heindl, A., & Telek, M., editors, Analytical and Stochastic Modeling Techniques and Applications, 15th International Conference, ASMTA 2008, Nicosia, Cyprus, Proceedings, volume 5055, of Lecture Notes in Computer Science, pages 249--263, Nicosia, Cyprus, June, 2008. Springer. 00023 bibtex: inproceedingsfernandes.fvw_pssan_08 bibtex[x-international-audience=yes;x-proceedings=yes;x-invited-conference=no]
abstract   bibtex   
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. Discreteevent 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.
@inproceedings{ fernandes_perfect_2008,
  address = {Nicosia, Cyprus},
  series = {Lecture {Notes} in {Computer} {Science}},
  title = {Perfect {Simulation} of {Stochastic} {Automata} {Networks}},
  volume = {5055},
  abstract = {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. Discreteevent 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.},
  booktitle = {Analytical and {Stochastic} {Modeling} {Techniques} and {Applications}, 15th {International} {Conference}, {ASMTA} 2008, {Nicosia}, {Cyprus}, {Proceedings}},
  publisher = {Springer},
  author = {Fernandes, Paulo and Vincent, Jean-Marc and Webber, Thais},
  editor = {Al-Begain, Khalid and Heindl, Armin and Telek, Miklόs},
  month = {June},
  year = {2008},
  note = {00023 bibtex: inproceedingsfernandes.fvw_pssan_08 
bibtex[x-international-audience=yes;x-proceedings=yes;x-invited-conference=no]},
  pages = {249--263}
}

Downloads: 0