Samy Abbes (Laboratoire PPS, université Paris Diderot)

Les empilements de pièces (heaps of pieces) sont des modèles étudiés en combinatoire d’une part, et dans le contexte de la théorie de la concurrence d’autre part (sous le nom de traces ou traces de Mazurkiewiscz). Dans ce contexte, un empilement modélise le déroulement d’un processus où certaines actions sont simultanées ; une application typique est l’analyse des accès concurrents à une base de données. Dans le cadre du model-checking de systèmes concurrents, aléatoires ou non, on a besoin de développer des outils probabilistes adaptés à la présence d’événements concurrents. Ce sont ces outils qui sont l’objet de cet exposé, à travers quelques questions concrètes.

On s’intéresse au problème de la génération uniforme d’empilements aléatoires de grande taille, et à l’évaluation moyenne d’une fonction de coût définie sur les empilements, lorsque la taille des empilements est grande.

Pour ce faire, on considère l’espace des empilements infinis. On montre qu’on peut approximer la distribution uniforme sur les empilements de taille k fixé assez grand, par une mesure de probabilité dite uniforme sur les empilements infinis. Cette mesure uniforme a de bien meilleures propriétés que la distribution uniforme sur les empilements de taille fixée, ce qui permet une résolution approchée des problèmes posés ci-dessus. En particulier, on peut donner une méthode d’approximation du speedup, c’est-à-dire le rapport entre le temps séquentiel et le temps parallèle d’exécution d’un processus concurrent aléatoire.