Skip to Main content Skip to Navigation

Perfect Sampling for Fork-Join networks.

Abstract : In this paper, we show how to design a perfect simulation for Markovian fork-join networks, or equivalently, free-choice Petri nets. For pure fork-join networks and for event graphs, the simulation time can be greatly reduced by using extremal initial states, namely blocking states, although such nets do not exhibit any natural monotonicity property. Another approach for perfect simulation of pure fork-join networks is based on a (max,plus) representation of the system. For that, we show how the theory of (max,plus) stochastic systems can be used to provide perfect samplings. Finally, experimental runs show that the (max,plus) approach couples within fewer steps but needs a larger simulation time than the Markovian approach.
Document type :
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download
Contributor : Colette Orange Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:09:02 AM
Last modification on : Saturday, September 11, 2021 - 3:19:17 AM


Files produced by the author(s)


  • HAL Id : hal-02101888, version 1



Anne Bouillard, Bruno Gaujal. Perfect Sampling for Fork-Join networks.. [Research Report] LIP RR-2005-12, Laboratoire de l'informatique du parallélisme. 2005, 2+14p. ⟨hal-02101888⟩



Les métriques sont temporairement indisponibles