Compositional Safe Approximation of Response Time Distribution of Complex Workflows

We propose a compositional technique for efficient evaluation of the cumulative distribution function of the response time of complex workflows, consisting of activities with generally distributed stochastic durations composed through sequence, choice/merge, split/join, and repetition blocks, with unbalanced split and join constructs that break the structure of well-formed nesting. Workflows are specified using a formalism defined in terms of stochastic Petri nets, that permits decomposition of the model into a hierarchy of sub-workflows with positively correlated response times, which guarantees a stochastically ordered approximation of the end-to-end response time when intermediate results are approximated by stochastically ordered distributions and when dependencies are simplified by replicating activities appearing in multiple sub-workflows. This opens the way to an efficient hierarchical solution that manages complex models by recursive application of Markov regenerative analysis and numerical composition of monovariate distributions.