Document Open Access Logo

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

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

PDF
Thumbnail PDF

File

LIPIcs.AofA.2018.14.pdf
  • Filesize: 0.51 MB
  • 14 pages

Document Identifiers

Author Details

Olivier Bodini
  • Laboratoire d'Informatique de Paris-Nord, CNRS UMR 7030 - Institut Galilée - Université Paris-Nord, 99, avenue Jean-Baptiste Clément, 93430 Villetaneuse, France.
Matthieu Dien
  • Institute of Statistical Science, Academia Sinica, Taipei 115, Taiwan.
Antoine Genitrini
  • Sorbonne Université, CNRS, Laboratoire d'Informatique de Paris 6 -LIP6- UMR 7606, F-75005 Paris, France.
Alfredo Viola
  • Universidad de la República, Montevideo, Uruguay.

Funding

This research was partially supported by the ANR MetACOnc project ANR-15-CE40-0014.

Cite As Get BibTex

Olivier Bodini, Matthieu Dien, Antoine Genitrini, and Alfredo Viola. Beyond Series-Parallel Concurrent Systems: The Case of Arch Processes. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.AofA.2018.14

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Generating functions
  • Theory of computation → Generating random combinatorial structures
  • Theory of computation → Concurrency
Keywords
  • Concurrency Theory
  • Future
  • Uniform Random Sampling
  • Unranking
  • Analytic Combinatorics

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. The ecmascript 2015 language specification, 2015. URL: http://www.ecma-international.org/ecma-262/6.0/index.html.
  2. M. Abramowitz and I. A. Stegun. Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. Dover, New York, ninth dover printing, tenth gpo printing edition, 1964. Google Scholar
  3. C. Baier and J.-P. Katoen. Principles of Model Checking (Representation and Mind Series). The MIT Press, 2008. Google Scholar
  4. H. C. Baker, Jr. and C. Hewitt. The incremental garbage collection of processes. In Proceedings of the 1977 Symposium on Artificial Intelligence and Programming Languages, pages 55-59. ACM, 1977. Google Scholar
  5. O. Bodini, M. Dien, X. Fontaine, A. Genitrini, and H.-K. Hwang. Increasing diamonds. In Latin American Symposium on Theoretical Informatics, pages 207-219. Springer, Berlin, Heidelberg, 2016. Google Scholar
  6. O. Bodini, M. Dien, A. Genitrini, and F. Peschanski. Entropic uniform sampling of linear extensions in series-parallel posets. In 12th International Computer Science Symposium in Russia (CSR), pages 71-84, 2017. Google Scholar
  7. O. Bodini, M. Dien, A. Genitrini, and F. Peschanski. The Ordered and Colored Products in Analytic Combinatorics: Application to the Quantitative Study of Synchronizations in Concurrent Processes. In 14th SIAM Meeting on Analytic Algorithmics and Combinatorics (ANALCO), pages 16-30, 2017. Google Scholar
  8. O. Bodini, A. Genitrini, and F. Peschanski. The combinatorics of non-determinism. In FSTTCS'13, volume 24 of LIPIcs, pages 425-436. Schloss Dagstuhl, 2013. Google Scholar
  9. O. Bodini, A. Genitrini, and F. Peschanski. A Quantitative Study of Pure Parallel Processes. Electronic Journal of Combinatorics, 23(1):P1.11, 39 pages, (electronic), 2016. Google Scholar
  10. G. Brightwell and P. Winkler. Counting linear extensions is ♯P-Complete. In STOC, pages 175-181, 1991. Google Scholar
  11. P. Flajolet and R. Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009. URL: http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=9780521898065.
  12. P. Flajolet, P. Zimmermann, and B. Van Cutsem. A calculus for the random generation of labelled combinatorial structures. Theoretical Computer Science, 132(1-2):1-35, 1994. Google Scholar
  13. R. Grosu and S. A. Smolka. Monte carlo model checking. In TACAS'05, volume 3440 of LNCS, pages 271-286. Springer, 2005. Google Scholar
  14. A. Khoroshkin and D. Piontkovski. On generating series of finitely presented operads. Journal of Algebra, 426:377-429, 2015. Google Scholar
  15. D. E. Knuth. The art of computer programming, volume 3: (2nd ed.) sorting and searching. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA, 1998. Google Scholar
  16. L. Lipshitz. The diagonal of a d-finite power series is d-finite. Journal of Algebra, 113(2):373-378, 1988. Google Scholar
  17. C. Martínez and X. Molinero. Generic algorithms for the generation of combinatorial objects. In MFCS'03, pages 572-581. Springer Berlin Heidelberg, 2003. Google Scholar
  18. R. Milner. A Calculus of Communicating Systems. Springer Verlag, 1980. Google Scholar
  19. R.W.D. Nickalls. Viète, descartes and the cubic equation. The Mathematical Gazette, 90(518):203–208, 2006. Google Scholar
  20. A. Nijenhuis and H.S. Wilf. Combinatorial algorithms. Computer science and applied mathematics. Academic Press, New York, NY, 1975. Google Scholar
  21. R.P. Stanley. Enumerative Combinatorics:. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2001. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact