Perfect Sampling for Fork-Join networks.

Anne Bouillard (1) , Bruno Gaujal (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

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.

Mots clés: Fork and join; Perfect simulation; Petri nets

Mots clés: Simulation parfaite; Réseau de Petri; Réseau de Fork et join

Domaines: Informatique [cs]

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⟩