DIEN Matthieu
Direction de recherche : Michèle SORIA
Processus concurrents et combinatoire des structures croissantes : analyse quantitative et algorithmes de génération aléatoire
Un programme concurrent est composé de plusieurs unités logiques : les processus. Chaque processus a un comportement qui lui est propre : il exécute ses actions de façon séquentielle.
Un objectif important est de s'assurer que de tels systèmes concurrents complexes soient cependant exempts de défaut. Cette problématique est étudiée dans le cadre de la théorie de la concurrence.
Quand plusieurs processus s’exécutent en parallèle, l’ordre d’exécution des actions du programme global n’est plus déterminé. On assiste au fameux phénomène "d’explosion combinatoire" faisant référence au très grand nombre d’exécutions globales possibles. Les diverses techniques et méthodes d'analyse existantes (model checking, analyse statique, tests automatisés, etc) se heurtent irrémédiablement à cette "explosion".
Cette thèse s'inscrit dans un projet à long terme d'étude quantitative de ce phénomène et de développement des techniques d’analyse statistique basées sur la génération aléatoire uniforme. Notre objectif dans cette thèse est de traiter une composante fondamentale de la concurrence : la synchronisation. Ce mécanisme permet aux processus de communiquer entre eux.
Dans cette thèse nous proposons un modèle combinatoire de structures croissantes pour modéliser les exécutions de programmes concurrents synchronisés. Avec des outils de combinatoire analytique nous obtenons plusieurs résultats exacts et asymptotiques sur le nombre moyen d'exécutions dans des sous-classes de programmes concurrents. Nous présentons aussi plusieurs algorithmes de génération aléatoire uniforme de structures croissantes et de leurs étiquetages.
Soutenance : 22/09/2017
Membres du jury :
M. Cyril NICAUD, Professeur Université Paris-Est, Marne-la-Vallée (Paris) [Rapporteur]
M. Alain DENISE, Professeur Université Paris-Sud (Paris) [Rapporteur]
M. Olivier BODINI, Professeur Université Paris-Nord (Paris)
M. Conrado MARTINEZ, Professeur Universitat Politècnica de Catalunya (Barcelone)
M. Antoine MINÉ, Professeur Université Pierre et Marie Curie (Paris)
M. Antoine GENITRINI, Maître de conférence & Université Pierre et Marie Curie (Paris)
M. Frédéric PESCHANSKI, Maître de conférence & Université Pierre et Marie Curie (Paris)
Mme Michèle SORIA, Professeur Université Pierre et Marie Curie (Paris)
Publications 2016-2022
-
2022
- M. Dien, A. Genitrini, F. Peschanski : “A Combinatorial Study of Async/Await Processes”, The 19th International Colloquium on Theoretical Aspects of Computing, vol. 13572, Lecture Notes in Computer Science, Tbilisi, Georgia, pp. 170-187, (Springer) (2022)
-
2021
- O. Bodini, M. Dien, A. Genitrini, F. Peschanski : “Quantitative and Algorithmic aspects of Barrier Synchronization in Concurrency”, Discrete Mathematics and Theoretical Computer Science, vol. vol. 22 no. 3, Computational Logic and Applications (CLA'19) (3), Computational Logic and Applications (CLA'19), (DMTCS) (2021)
-
2019
- O. Bodini, M. Dien, A. Genitrini, F. Peschanski : “The Combinatorics of Barrier Synchronization”, PETRI NETS 2019 - 40th International Conference on Application and Theory of Petri Nets and Concurrency, vol. 11522, Lecture Notes in Computer Science, Aachen, Germany, pp. 386-405 (2019)
-
2018
- O. Bodini, A. Genitrini, M. Dien, A. Viola : “Beyond series-parallel concurrent systems: the case of arch processes”, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018), vol. 110, Leibniz International Proceedings in Informatics (LIPIcs), Uppsala, Sweden, pp. 14:1-14:14 (2018)
-
2017
- M. Dien : “Processus concurrents et combinatoire des structures croissantes : analyse quantitative et algorithmes de génération aléatoire”, thèse, soutenance 22/09/2017, direction de recherche Soria, Michèle (2017)
- O. Bodini, M. Dien, A. Genitrini, F. Peschanski : “The Ordered and Colored Products in Analytic Combinatorics: Application to the Quantitative Study of Synchronizations in Concurrent Processes”, 2017 Proceedings of the Fourteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), Barcelone, Spain, pp. 16-30 (2017)
- O. Bodini, M. Dien, A. Genitrini, F. Peschanski : “Entropic Uniform Sampling of Linear Extensions in Series-Parallel Posets”, Computer Science Symposium in Russia, Kazan, Russian Federation (2017)
-
2016
- O. Bodini, M. Dien, X. Fontaine, A. Genitrini, H.‑K. Hwang : “Increasing Diamonds”, 12th. Latin American Theoretical INformatics Symposium, Ensenada, Mexico (2016)