Quantitative and Algorithmic aspects of Barrier Synchronization in Concurrency
| Autor: | Antoine Genitrini, Matthieu Dien, Frédéric Peschanski, Olivier Bodini |
|---|---|
| Přispěvatelé: | Laboratoire d'Informatique de Paris-Nord (LIPN), Institut Galilée-Université Sorbonne Paris Cité (USPC)-Centre National de la Recherche Scientifique (CNRS)-Université Sorbonne Paris Nord, Equipe AMACC - Laboratoire GREYC - UMR6072, Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen (GREYC), Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Normandie Université (NU)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS), Algorithmes, Programmes et Résolution (APR), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Université Sorbonne Paris Nord, Groupe de Recherche en Informatique, Image et Instrumentation de Caen (GREYC), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Normandie Université (NU)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU) |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
Theoretical computer science
Partial Order Theory General Computer Science Process (engineering) Concurrency [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] Fork-Join processes [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] Theoretical Computer Science Promises Simple (abstract algebra) Combinatorics Synchronization (computer science) Decomposition (computer science) Discrete Mathematics and Combinatorics Graph (abstract data type) Point (geometry) Uniform random generation Barrier synchronization Combinatorial explosion Mathematics |
| Zdroj: | HAL Discrete Mathematics and Theoretical Computer Science Discrete Mathematics and Theoretical Computer Science, DMTCS, In press, Computational Logic and Applications (CLA'19), 22 (3) |
| ISSN: | 1462-7264 1365-8050 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|