Dirección de investigación : 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.

Publicaciones 2020-2022