Statistical Analysis of Non-Deterministic Fork-Join Processes - Sorbonne Université
Communication Dans Un Congrès Année : 2020

Statistical Analysis of Non-Deterministic Fork-Join Processes

Antoine Genitrini
Martin Pépin

Résumé

We study the combinatorial structure of the state-space of non-deterministic fork-join processes. As a first step we establish a link between concurrent programs and a class of combinatorial structures based on the notion of increasing labelling. Beyond the theory, our goal is to develop algorithms and tools for the statistical analysis of the process behaviours. In the second part we develop and experiment two efficient random sampling algorithms serving as basic building blocks for state-space exploration. One is a uniform random sampler of bounded executions, providing a good default exploration strategy, and the other is a uniform sampler of execution prefixes allowing to bias the exploration in a controlled manner. The fundamental characteristic of these algorithms is that they work on the control graph of the programs and do not require the construction of its state-space, thus providing a way to tackle the infamous state explosion problem.
Fichier principal
Vignette du fichier
ictac2020.pdf (413.21 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02659801 , version 1 (30-05-2020)
hal-02659801 , version 2 (21-10-2020)

Identifiants

Citer

Antoine Genitrini, Martin Pépin, Frédéric Peschanski. Statistical Analysis of Non-Deterministic Fork-Join Processes. Theoretical Aspects of Computing - ICTAC 2020 - 17th International Colloquium, Nov 2020, Macau, China. pp.83-102, ⟨10.1007/978-3-030-64276-1_5⟩. ⟨hal-02659801v2⟩
280 Consultations
151 Téléchargements

Altmetric

Partager

More