DIEN Matthieu

PhD graduated
Team : APR
Departure date : 09/30/2017

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)

2016-2021 Publications