License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AofA.2018.14
URN: urn:nbn:de:0030-drops-89075
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8907/
Go to the corresponding LIPIcs Volume Portal

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

Beyond Series-Parallel Concurrent Systems: The Case of Arch Processes

pdf-format:
LIPIcs-AofA-2018-14.pdf (0.5 MB)

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 is a directed acyclic graph (DAG). Since the quantitative study of increasingly labeled DAG (directly related to processes) seems out of reach (this is a #P-complete problem), 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 classical 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 a uniform random sampler algorithm and an unranking one that allow efficient generation and exhaustive enumeration of the runs of a given arch process.

BibTeX - Entry

@InProceedings{bodini_et_al:LIPIcs:2018:8907,
  author =	{Olivier Bodini and Matthieu Dien and Antoine Genitrini and Alfredo Viola},
  title =	{{Beyond Series-Parallel Concurrent Systems: The Case of Arch Processes}},
  booktitle =	{29th International Conference on Probabilistic,  Combinatorial and Asymptotic Methods for the Analysis of Algorithms  (AofA 2018)},
  pages =	{14:1--14:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{James Allen Fill and Mark Daniel Ward},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8907},
  URN =		{urn:nbn:de:0030-drops-89075},
  doi =		{10.4230/LIPIcs.AofA.2018.14},
  annote =	{Keywords: Concurrency Theory, Future, Uniform Random Sampling, Unranking, Analytic Combinatorics}
}

Keywords: Concurrency Theory, Future, Uniform Random Sampling, Unranking, Analytic Combinatorics
Collection: 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)
Issue Date: 2018
Date of publication: 18.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI