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 :
Reports
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101888
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:09:02 AM
Last modification on : Friday, May 17, 2019 - 1:39:22 AM

File

RR2005-12.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101888, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

4

Files downloads

7