Backward Coupling in Bounded Free-Choice Nets Under Markovian and Non-Markovian Assumptions

Anne Bouillard 1 Bruno Gaujal 2
1 DISTRIBCOM - Distributed and Iterative Algorithms for the Management of Telecommunications Systems
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
2 MESCAL - Middleware efficiently scalable
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : In this paper, we show how to design a perfect sampling algorithm for stochastic Free-Choice Petri nets by backward coupling. For Markovian event graphs, the simulation time can be greatly reduced by using extremal initial states, namely blocking marking, although such nets do not exhibit any natural monotonicity property. Another approach for perfect simulation of non-Markovian event graphs is based on a (max,plus) representation of the system and the theory of (max,plus) stochastic systems. We also show how to extend this approach to one-bounded free choice nets to the expense of keeping all states. Finally, experimental runs show that the (max,plus) approach needs a larger simulation time than the Markovian approach.
Type de document :
Article dans une revue
Journal of Discrete Event Dynamics Systems, theory and applications, Springer, 2008, 18, pp.473-498. 〈10.1007/s10626-008-0041-8〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00953608
Contributeur : Arnaud Legrand <>
Soumis le : vendredi 28 février 2014 - 14:11:03
Dernière modification le : mercredi 16 mai 2018 - 11:23:02

Lien texte intégral

Identifiants

Citation

Anne Bouillard, Bruno Gaujal. Backward Coupling in Bounded Free-Choice Nets Under Markovian and Non-Markovian Assumptions. Journal of Discrete Event Dynamics Systems, theory and applications, Springer, 2008, 18, pp.473-498. 〈10.1007/s10626-008-0041-8〉. 〈hal-00953608〉

Partager

Métriques

Consultations de la notice

300