Direction de recherche : Antoine GENITRINI

Génération aléatoire uniforme de trajectoires dans les systèmes concurrents

Dans cette thèse nous étudions l'espace d'état des programmes concurrents à l'aide des outils de la combinatoire analytique. Dans un premier temps nous analysons une classe de programmes utilisant du parallélisme, du choix non-déterministe, des boucles et de la synchronisation de type fork-join. Pour cette classe nous proposons des résultats quantitatifs sur l'explosion combinatoire de l'espace d'état et des outils algorithmiques efficaces de génération aléatoire uniforme d'exécutions.

Dans un second temps nous étudions une nouvelle classe de graphes dirigés sans cycles en tant qu'approximation des ordres partiels, eux mêmes modélisant fidèlement le flot de contrôle des programmes concurrents. Pour cette classe nous proposons un algorithme de génération aléatoire uniforme efficace à nombre de sommets et d'arêtes fixés.

Finalement, nous étudions aussi des aspects algorithmiques et pratiques de la génération aléatoire dont le champ d'application dépasse le cadre de la concurrence.

Soutenance : 29/09/2021

Membres du jury :

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é)

Publications 2020-2022

• 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”, soutenance de thèse, soutenance 29/09/2021, direction de recherche 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, (Elsevier) (2021)
• 2020
  • A. Genitrini, M. Pépin, F. Peschanski : “Statistical Analysis of Non-Deterministic Fork-Join Processes”, Theoretical Aspects of Computing - ICTAC 2020 - 17^th International Colloquium, vol. 12545, Lecture Notes in Computer Science, Macau, China, pp. 83-102, (Springer) (2020)