PEPIN Martin
Supervision : Antoine GENITRINI
Quantitative and algorithmic analysis of concurrent programs
In this thesis, we study the state space of concurrent programs using tools from analytic combinatorics. First, we study a class of programs featuring parallelism, non-deterministic choice, loops and a fork-join style of synchronisation. For this class, we propose quantitative results regarding the combinatorial explosion of the state space and efficient algorithmic tools for the uniform random generation of executions.
Then, we study a new class of directed acyclic graphs, which are related to the control-flow of concurrent programs as an encoding of partial orders. For this class, we propose a efficient uniform random sampling algorithm with a given number of edges and vertices.
Finally, we also study various algorithmic and practical aspects of random generation whose field of application goes beyond the scope of concurrency.
Defence : 09/29/2021
Jury members :
KAUERS Manuel (Johannes Kepler University) [Rapporteur]
RAVELOMANANA Vlady (Université de Paris) [Rapporteur]
BODINI Olivier (Université Paris-Nord)
GENITRINI Antoine (Sorbonne Université)
PESCHANSKI Frédéric (Sorbonne Université)
POITRENAUD Denis (Université de Paris)
PONS Viviane (Université Paris-Saclay)
TASSON Christine (Sorbonne Université)
2020-2022 Publications
-
2022
- A. Genitrini, M. Pépin, F. Peschanski : “A quantitative study of fork-join processes with non-deterministic choice: application to the statistical exploration of the state-space”, Theoretical Computer Science, vol. 912, pp. 1-36, (Elsevier) (2022)
-
2021
- M. Pepin : “Quantitative and algorithmic analysis of concurrent programs”, thesis, defence 09/29/2021, supervision Genitrini, Antoine (2021)
- A. Genitrini, M. Pépin : “Lexicographic unranking of combinations revisited”, Algorithms, vol. 14 (3), pp. 97, (MDPI) (2021)
- A. Genitrini, M. Pépin, A. Viola : “Unlabelled ordered DAGs and labelled DAGs: constructive enumeration and uniform random sampling”, Procedia Computer Science, vol. 195, Proceedings of the XI Latin and American Algorithms, Graphs and Optimization Symposium, Sao Paulo, Brazil, pp. 468-477 (2021)
-
2020
- A. Genitrini, M. Pépin, F. Peschanski : “Statistical Analysis of Non-Deterministic Fork-Join Processes”, Theoretical Aspects of Computing - ICTAC 2020 - 17th International Colloquium, vol. 12545, Lecture Notes in Computer Science, Macau, China, pp. 83-102, (Springer) (2020)