A quantitative study of pure parallel processes

MaRDI QIDQ907263zbMATH OpenFDO

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

Publication date 25 January 2016

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.1873, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p11

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

analytic combinatoricsrandom generationconcurrency theoryincreasing treesholonomic functionsinterleaving semanticspure merge

Mathematics Subject Classification ID

Trees (05C05) Asymptotic enumeration (05A16) Combinatorics of partially ordered sets (06A07) Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.) (68N19)

Abstract: In this paper, we study the interleaving -- or pure merge -- operator that most often characterizes parallelism in concurrency theory. This operator is a principal cause of the so-called combinatorial explosion that makes very hard - at least from the point of view of computational complexity - the analysis of process behaviours e.g. by model-checking. The originality of our approach is to study this combinatorial explosion phenomenon on average, relying on advanced analytic combinatorics techniques. We study various measures that contribute to a better understanding of the process behaviours represented as plane rooted trees: the number of runs (corresponding to the width of the trees), the expected total size of the trees as well as their overall shape. Two practical outcomes of our quantitative study are also presented: (1) a linear-time algorithm to compute the probability of a concurrent run prefix, and (2) an efficient algorithm for uniform random sampling of concurrent runs. These provide interesting responses to the combinatorial explosion problem.

Recommendations

• Associativity for binary parallel processes: a quantitative study
• Enumeration and random generation of concurrent computations
• The Combinatorics of Non-determinism
• A quantitative study of fork-join processes with non-deterministic choice: application to the statistical exploration of the state-space
• Beyond series-parallel concurrent systems: the case of arch processes

Cites work

• scientific article; zbMATH DE number 3114505 (Why is no real title available?)
• scientific article; zbMATH DE number 140457 (Why is no real title available?)
• scientific article; zbMATH DE number 1099195 (Why is no real title available?)
• scientific article; zbMATH DE number 3443655 (Why is no real title available?)
• scientific article; zbMATH DE number 7088727 (Why is no real title available?)
• scientific article; zbMATH DE number 3319665 (Why is no real title available?)
• A holonomic systems approach to special functions identities
• An Efficient Method for Weighted Sampling without Replacement
• Analytic aspects of the shuffle product
• Analytic combinatorics
• Associativity for binary parallel processes: a quantitative study
• Automatic verification of finite-state concurrent systems using temporal logic specifications
• Biased Boltzmann samplers and generation of extended linear languages with shuffle
• Birthday paradox, coupon collectors, caching algorithms and self- organizing search
• Calcul pratique des coefficients de Taylor d'une fonction algébrique
• Differentiably finite power series
• Dyck tilings, increasing trees, descents, and inversions
• Enumeration and random generation of concurrent computations
• Fast perfect sampling from linear extensions
• GFUN
• Hopf algebras, renormalization and noncommutative geometry
• Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen
• Linear extension sums as valuations on cones
• Multiset theory
• Noncommutative symmetric functions. VII: Free quasi-symmetric functions revisited
• On computing the number of linear extensions of a tree
• On the Altitude of Nodes in Random Trees
• On the number of trees in a random forest
• Process Algebra
• Random Trees
• The Combinatorics of Non-determinism
• The Saga of the Axiomatization of Parallel Composition
• Tools and Algorithms for the Construction and Analysis of Systems
• Twelve countings with rooted plane trees

Cited in

(13)

• A quantitative study of fork-join processes with non-deterministic choice: application to the statistical exploration of the state-space
• scientific article; zbMATH DE number 7524075 (Why is no real title available?)
• Extended boxed product and application to synchronized trees
• Beyond series-parallel concurrent systems: the case of arch processes
• Untanglings: a novel approach to analyzing concurrent systems
• Associativity for binary parallel processes: a quantitative study
• The Combinatorics of Barrier Synchronization
• Enumeration and random generation of concurrent computations
• scientific article; zbMATH DE number 795729 (Why is no real title available?)
• Entropic uniform sampling of linear extensions in series-parallel posets
• Compaction for two models of logarithmic‐depth trees: Analysis and experiments
• scientific article; zbMATH DE number 2172786 (Why is no real title available?)
• Parallel processes with implicit computational capital

This page was built for publication: A quantitative study of pure parallel processes

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