Geodesic
Quantitative and Algorithmic aspects of Barrier Synchronization in Concurrency
Discrete mathematics & theoretical computer science, Computational Logic and Applications (CLA'19), Tome 22 (2020-2021) no. 3.

Voir la notice de l'article provenant de la source Episciences

In this paper we address the problem of understanding Concurrency Theory from a combinatorial point of view. We are interested in quantitative results and algorithmic tools to refine our understanding of the classical combinatorial explosion phenomenon arising in concurrency. This paper is essentially focusing on the the notion of synchronization from the point of view of combinatorics. As a first step, we address the quantitative problem of counting the number of executions of simple processes interacting with synchronization barriers. We elaborate a systematic decomposition of processes that produces a symbolic integral formula to solve the problem. Based on this procedure, we develop a generic algorithm to generate process executions uniformly at random. For some interesting sub-classes of processes we propose very efficient counting and random sampling algorithms. All these algorithms have one important characteristic in common: they work on the control graph of processes and thus do not require the explicit construction of the state-space. 
@article{DMTCS_2021_22_3_a0,
     author = {Bodini, OLivier and Dien, Matthieu and Genitrini, Antoine and Peschanski, Fr\'ed\'eric},
     title = {Quantitative and {Algorithmic} aspects of {Barrier} {Synchronization} in {Concurrency}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {22},
     number = {3},
     year = {2020-2021},
     doi = {10.46298/dmtcs.5820},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.5820/}
}
TY  - JOUR
AU  - Bodini, OLivier
AU  - Dien, Matthieu
AU  - Genitrini, Antoine
AU  - Peschanski, Frédéric
TI  - Quantitative and Algorithmic aspects of Barrier Synchronization in Concurrency
JO  - Discrete mathematics & theoretical computer science
PY  - 2020-2021
VL  - 22
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.5820/
DO  - 10.46298/dmtcs.5820
LA  - en
ID  - DMTCS_2021_22_3_a0
ER  - 
%0 Journal Article
%A Bodini, OLivier
%A Dien, Matthieu
%A Genitrini, Antoine
%A Peschanski, Frédéric
%T Quantitative and Algorithmic aspects of Barrier Synchronization in Concurrency
%J Discrete mathematics & theoretical computer science
%D 2020-2021
%V 22
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.5820/
%R 10.46298/dmtcs.5820
%G en
%F DMTCS_2021_22_3_a0
Bodini, OLivier; Dien, Matthieu; Genitrini, Antoine; Peschanski, Frédéric. Quantitative and Algorithmic aspects of Barrier Synchronization in Concurrency. Discrete mathematics & theoretical computer science, Computational Logic and Applications (CLA'19), Tome 22 (2020-2021) no. 3. doi : 10.46298/dmtcs.5820. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.5820/

Cité par Sources :