The Combinatorics of Barrier Synchronization

DOI10.1007/978-3-030-21571-2_21MaRDI QIDQ6144224zbMATH OpenFDO

Authors Olivier Bodini, Matthieu Dien, Antoine Genitrini, Frédéric Peschanski

Publication date 29 January 2024

Published in Application and Theory of Petri Nets and Concurrency (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.04243

zbMATH Keywords

barrier synchronizationuniform random generation

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Combinatorics in computer science (68R05) Nonnumerical algorithms (68W05)

Abstract: In this paper we study 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.

Recommendations

• Quantitative and algorithmic aspects of barrier synchronization in concurrency
• Comparing barrier algorithms
• A network model of Barrier synchronization algorithms
• Noncommittal barrier synchronization
• A quantitative study of pure parallel processes

Cites work

• A calculus for the random generation of labelled combinatorial structures
• A quantitative study of pure parallel processes
• Beyond series-parallel concurrent systems: the case of arch processes
• Entropic uniform sampling of linear extensions in series-parallel posets
• Fast perfect sampling from linear extensions
• scientific article; zbMATH DE number 7204953 (Why is no real title available?)
• The Combinatorics of Non-determinism
• Tools and Algorithms for the Construction and Analysis of Systems
• Two algorithms for barrier synchronization
• Two poset polytopes
• Uniform generation in trace monoids

Cited in

(1)

• Quantitative and algorithmic aspects of barrier synchronization in concurrency

This page was built for publication: The Combinatorics of Barrier Synchronization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6144224)