Supervision : Michèle SORIA
Concurrent process and combinatorics of increasingly labeled structures: quantitative analysis and random generation algorithms.
A concurrent program is a composition of several logical blocks: the processes. Each process has its own behavior, independent from the others: it sequentially runs its actions.
An important goal is to ensure that such concurrent complex systems are faultless. This problem is studied in the field of concurrency theory.
When several process are running in parallel, the running order of the actions of the total program is no more decided. This is the well-known "combinatorial explosion" phenomena, meaning that the number of possible runs of the global program is huge. The analysis techniques and methods existing (model checking, static analysis, automated testing, etc) are irremediably limited by this "explosion".
This thesis is a part of a long-term project about the quantitative study of this phenomena and the development of statistic analysis methods based on the uniform random generation. Our specific goal is to study a fundamental principle of the concurrency theory: the synchronization. This mechanism allows communications between the processes.
In this thesis we propose a combinatorial model of increasingly labeled structures to deal with runs of synchronized concurrent programs. Using the tools of analytic combinatorics we obtain close formulas and asymptotic equivalents for the average number of runs in several subclasses of concurrent programs. We also present algorithms of uniform random generation of increasingly labeled structures and for their increasing labelings.
Defence : 09/22/2017 - 16h30 - Site Jussieu 15-16/101
Jury members :
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)
- 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)
- 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)
- 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)
- M. Dien : “Processus concurrents et combinatoire des structures croissantes : analyse quantitative et algorithmes de génération aléatoire”, thesis, defence 09/22/2017, supervision 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)
- O. Bodini, M. Dien, X. Fontaine, A. Genitrini, H.‑K. Hwang : “Increasing Diamonds”, 12th. Latin American Theoretical INformatics Symposium, Ensenada, Mexico (2016)