A quantitative study of pure parallel processes (Q907263)

From MaRDI portal
Revision as of 17:53, 18 April 2024 by Importer (talk | contribs) (‎Changed an Item)
scientific article
Language Label Description Also known as
English
A quantitative study of pure parallel processes
scientific article

    Statements

    A quantitative study of pure parallel processes (English)
    0 references
    0 references
    0 references
    0 references
    25 January 2016
    0 references
    Summary: 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 the analysis of process behaviours e.g. by model-checking, very hard -- at least from the point of view of computational complexity. 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.
    0 references
    pure merge
    0 references
    interleaving semantics
    0 references
    concurrency theory
    0 references
    analytic combinatorics
    0 references
    increasing trees
    0 references
    holonomic functions
    0 references
    random generation
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references