PEPIN Martin

PhD graduated
Team : APR
Departure date : 08/31/2021

Supervision : Antoine GENITRINI

Quantitative and algorithmic analysis of concurrent programs

In this thesis, we study the state space of concurrent programs using tools from analytic combinatorics. First, we study a class of programs featuring parallelism, non-deterministic choice, loops and a fork-join style of synchronisation. For this class, we propose quantitative results regarding the combinatorial explosion of the state space and efficient algorithmic tools for the uniform random generation of executions.
Then, we study a new class of directed acyclic graphs, which are related to the control-flow of concurrent programs as an encoding of partial orders. For this class, we propose a efficient uniform random sampling algorithm with a given number of edges and vertices.
Finally, we also study various algorithmic and practical aspects of random generation whose field of application goes beyond the scope of concurrency.

Defence : 09/29/2021

Jury members :

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

Departure date : 08/31/2021

2020-2022 Publications