OLivier Bodini ; Matthieu Dien ; Antoine Genitrini ; Frédéric Peschanski - Quantitative and Algorithmic aspects of Barrier Synchronization in Concurrency

dmtcs:5820 - Discrete Mathematics & Theoretical Computer Science, January 25, 2021, vol. 22 no. 3, Computational Logic and Applications (CLA'19) - https://doi.org/10.46298/dmtcs.5820
Quantitative and Algorithmic aspects of Barrier Synchronization in ConcurrencyArticle

Authors: OLivier Bodini ; Matthieu Dien 1; Antoine Genitrini 2; Frédéric Peschanski ORCID2

  • 1 Equipe AMACC - Laboratoire GREYC - UMR6072
  • 2 Algorithmes, Programmes et Résolution

In this paper we address the problem of understanding Concurrency Theory from a combinatorial point of view. We are interested in quantitative results and algorithmic tools to refine our understanding of the classical combinatorial explosion phenomenon arising in concurrency. This paper is essentially focusing on the the notion of synchronization from the point of view of combinatorics. As a first step, we address the quantitative problem of counting the number of executions of simple processes interacting with synchronization barriers. We elaborate a systematic decomposition of processes that produces a symbolic integral formula to solve the problem. Based on this procedure, we develop a generic algorithm to generate process executions uniformly at random. For some interesting sub-classes of processes we propose very efficient counting and random sampling algorithms. All these algorithms have one important characteristic in common: they work on the control graph of processes and thus do not require the explicit construction of the state-space.

Volume: vol. 22 no. 3, Computational Logic and Applications (CLA'19)
Section: Special issues
Published on: January 25, 2021
Accepted on: January 8, 2021
Submitted on: October 9, 2019
Keywords: Uniform random generation,Fork-Join processes,Promises,Partial Order Theory,Barrier synchronization,Combinatorics,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
    Source : OpenAIRE Graph
  • Non conventional Analytic methods for Combinatorics; Funder: French National Research Agency (ANR); Code: ANR-15-CE40-0014

Consultation statistics

This page has been seen 610 times.
This article's PDF has been downloaded 397 times.