Beyond series-parallel concurrent systems: the case of arch processes
Preprint
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.Keywords
All Related Versions
This publication has 5 references indexed in Scilit:
- A Quantitative Study of Pure Parallel ProcessesThe Electronic Journal of Combinatorics, 2016
- On generating series of finitely presented operadsJournal of Algebra, 2015
- Generic Algorithms for the Generation of Combinatorial ObjectsLecture Notes in Computer Science, 2003
- A calculus for the random generation of labelled combinatorial structuresTheoretical Computer Science, 1994
- The diagonal of a D-finite power series is D-finiteJournal of Algebra, 1988