Beyond series-parallel concurrent systems: the case of arch processes

DOI10.4230/LIPICS.AOFA.2018.14MaRDI QIDQ4993536zbMATH OpenOpenAlexFDO

Authors Olivier Bodini, Matthieu Dien, Antoine Genitrini, Alfredo Viola

Publication date 15 June 2021

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

zbMATH Keywords

analytic combinatoricsconcurrency theoryfutureuniform random samplingunranking

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: In this paper we focus on concurrent processes built on synchronization by means of futures. This concept is an abstraction for processes based on a main execution thread but allowing to delay some computations. The structure of a general concurrent process with futures is more or less a directed acyclic graph. Since the quantitative study of such increasingly labeled graphs (directly related to processes) seems out of reach, we restrict ourselves to the study of arch processes, a simplistic model of processes with futures. They are based on two parameters related to their sizes and their numbers of arches. The increasingly labeled structures seems not to be specifiable in the sense of Analytic Combinatorics, but we manage to derive a recurrence equation for the enumeration. For this model we first exhibit an exact and an asymptotic formula for the number of runs of a given process. The second main contribution is composed of an uniform random sampler algorithm and an unranking one that allow efficient generation and exhaustive enumeration of the runs of a given arch process.

Recommendations

• Enumeration and random generation of concurrent computations
• A quantitative study of pure parallel processes
• Associativity for binary parallel processes: a quantitative study
• scientific article; zbMATH DE number 17542
• A quantitative study of fork-join processes with non-deterministic choice: application to the statistical exploration of the state-space

Cites work

• A calculus for the random generation of labelled combinatorial structures
• A calculus of communicating systems
• A quantitative study of pure parallel processes
• Analytic combinatorics
• Entropic uniform sampling of linear extensions in series-parallel posets
• Enumerative combinatorics. Volume 2.
• scientific article; zbMATH DE number 3535592 (Why is no real title available?)
• scientific article; zbMATH DE number 5585443 (Why is no real title available?)
• scientific article; zbMATH DE number 3273551 (Why is no real title available?)
• Increasing diamonds
• Mathematical Foundations of Computer Science 2003
• On generating series of finitely presented operads
• The Combinatorics of Non-determinism
• The diagonal of a D-finite power series is D-finite
• Tools and Algorithms for the Construction and Analysis of Systems

Cited in

(8)

• A quantitative study of fork-join processes with non-deterministic choice: application to the statistical exploration of the state-space
• Strict monotonic trees arising from evolutionary processes: combinatorial and probabilistic study
• Increasing diamonds
• Enumeration and random generation of concurrent computations
• Quantitative and algorithmic aspects of barrier synchronization in concurrency
• Associativity for binary parallel processes: a quantitative study
• The Combinatorics of Barrier Synchronization
• A quantitative study of pure parallel processes

This page was built for publication: Beyond series-parallel concurrent systems: the case of arch processes

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