On Probabilistic Parallel Programs with Process Creation and Synchronisation

Details On Probabilistic Parallel Programs with Process Creation and Synchronisation On Probabilistic Parallel Programs with Process Creation and Synchronisation

2010-12-14

arxiv.org/abs/1012.2998v1

Computer Science

Logic in Computer Science

This is a technical report accompanying a TACAS'11 paper

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On Probabilistic Parallel Programs with Process Creation and Synchronisation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Probabilistic Parallel Programs with Process Creation and Synchronisation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Probabilistic Parallel Programs with Process Creation and Synchronisation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-179394