On probabilistic parallel programs with process creation and synchronisation

DOI10.1007/978-3-642-19835-9_28MaRDI QIDQ3000662zbMATH OpenOpenAlexFDO

Authors Stefan Kiefer, Dominik Wojtczak

Publication date 19 May 2011

Published in Tools and Algorithms for the Construction and Analysis of Systems (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.) (68N19) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: We initiate the study of probabilistic parallel programs with dynamic process creation and synchronisation. To this end, we introduce probabilistic split-join systems (pSJSs), a model for parallel programs, generalising both probabilistic pushdown systems (a model for sequential probabilistic procedural programs which is equivalent to recursive Markov chains) and stochastic branching processes (a classical mathematical model with applications in various areas such as biology, physics, and language processing). Our pSJS model allows for a possibly recursive spawning of parallel processes; the spawned processes can synchronise and return values. We study the basic performance measures of pSJSs, especially the distribution and expectation of space, work and time. Our results extend and improve previously known results on the subsumed models. We also show how to do performance analysis in practice, and present two case studies illustrating the modelling power of pSJSs.

Recommendations

• Analysis of probabilistic basic parallel processes
• scientific article; zbMATH DE number 1231560
• scientific article; zbMATH DE number 1324652
• scientific article; zbMATH DE number 3999272
• Concurrent Probabilistic Programs, Or: How to Schedule If You Must

Cites work

• scientific article; zbMATH DE number 3410334 (Why is no real title available?)
• scientific article; zbMATH DE number 3190745 (Why is no real title available?)
• CONCUR 2005 – Concurrency Theory
• Computing the least fixed point of positive polynomial systems
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Local Versus Global Strategies for Adaptive Quadrature
• On probabilistic parallel programs with process creation and synchronisation
• On the Complexity of Numerical Analysis
• On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
• On the memory consumption of probabilistic pushdown automata
• Process rewrite systems.
• Programming with exceptions in JCilk
• Reachability problems on regular ground tree rewriting graphs
• Recursive Concurrent Stochastic Games
• Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations
• Tools and Algorithms for the Construction and Analysis of Systems

Cited in

(4)

• Model-free reinforcement learning for branching Markov decision processes
• On probabilistic parallel programs with process creation and synchronisation
• Analysis of probabilistic basic parallel processes
• Identity testing for radical expressions

This page was built for publication: On probabilistic parallel programs with process creation and synchronisation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3000662)