Perfect Sampling for Fork-Join networks. - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2005

Perfect Sampling for Fork-Join networks.

(1) , (1)
1

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.
Dans cet article, nous montrons comment simuler de manière exacte les réseaux fork-join markoviens, ou réseaux de Petri à choix libres. Pour les réseaux fork-join purs, ou graphes d’ événements, le temps de simulation peut être très fortement réduit en utilisant des états initiaux extrémaux,bien que ces réseaux ne satisfassent aucune propriété naturelle de monotonicité. Une autre approche pour la simulation parfaite des réseaux fork-join purs est basée sur la représentation (max,plus) de ces systèmes.Pour cela, nous montrons comment la théorie (max,plus) des systèmes stochastiques peut être utilisée pour fournir une simulation parfaite. Enfin, des expérimentations montrent que l’approche (max,plus) couple en moins d’ étapes, mais nécessite un temps d’exécution plus long que l’approche markoviene.
Fichier principal
Vignette du fichier
RR2005-12.pdf (275.66 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-02101888 , version 1 (17-04-2019)

Identifiers

  • HAL Id : hal-02101888 , version 1

Cite

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⟩
36 View
62 Download

Share

Gmail Facebook Twitter LinkedIn More