A quantitative study of pure parallel processes

zbMATH Open1329.05066arXiv1407.1873MaRDI QIDQ907263FDOQ907263

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)

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.

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

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

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

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)

Cites Work

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

Cited In (13)

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

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)