责任导师 : 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.

2016-2022 刊物

• 2022
  • M. Dien, A. Genitrini, F. Peschanski : “A Combinatorial Study of Async/Await Processes”, The 19^th 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 - 40^th 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”, 29^th 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”, 博士论文, 答辩 2017-9-22, 责任导师 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”, 12^th. Latin American Theoretical INformatics Symposium, Ensenada, Mexico (2016)