Compositional safe approximation of response time distribution of complex workflows

Abstract: 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.

Proceedings of QEST, pp. 83-104, Springer, 2021
Stochastic ProcessesPerformance ModelsStochastic WorkflowsApplications



copy bib | save bib | save pdf | go to publisher

🏠 Home