Matthieu Dien (GREYC, Caen)

Quand plusieurs processus concurrents s’exécutent en parallèle, l’ordre d’exécution des actions du programme global n’est plus déterminé. On assiste au fameux phénomène “d’explosion combinatoire” faisant référence au très grand nombre d’exécutions globales possibles. Les diverses techniques et méthodes d’analyse existantes (model checking, analyse statique, tests automatisés, etc) se heurtent irrémédiablement à cette “explosion”.

Dans cet exposé, nous étudierons ce phénomène d’un point de vue combinatoire en proposant des modèles, de plus en plus riches, permettant d’étudier différentes sous-classes de programmes concurrents. Nous présenterons aussi des algorithmes de génération aléatoire uniforme d’exécutions de programmes concurrents pour ces différentes sous-classes.