Compositional Evaluation of Stochastic Workflows for Response Time Analysis of Composite Web Services

Workflows are patterns of orchestrated activities designed to deliver some specific output, with application in various relevant contexts including software services, business processes, supply chain management. In most of these scenarios, durational properties of individual activities can be identified from logged data and cast in stochastic models, enabling quantitative evaluation of time behavior for diagnostic and predictive analytics. However, effective fitting of observed durations commonly requires that distributions break the limits of memoryless behavior and unbounded support of Exponential distributions, casting the problem in the class of non-Markovian models. This results in a major hurdle for numerical solution, largely exacerbated by the concurrency structure of workflows, which natively subtend concurrent activities with overlapping execution intervals and a limited number of regeneration points, i.e., time points at which the Markov property is satisfied and analysis can be decomposed according to a renewal argument. We propose a compositional method for quantitative evaluation of end-To-end response time of complex workflows. The workflow is modeled through Stochastic Time Petri Nets (STPNs), associating activity durations with Exponential distributions truncated over bilateral firmly bounded supports that fit mean and coefficient of variation of real logged histograms. Based on the model structure, the workflow is decomposed into a hierarchy of subworkflows, each amenable to efficient numerical solution through Markov regenerative transient analysis. In this step, the grain of decomposition is driven by non-deterministic analysis of the space of feasible behaviors in the underlying Time Petri Net (TPN) model, which permits efficient characterization of the factors that affect behavior complexity between regeneration points. Duration distributions of the subworkflows obtained through separate analyses are then repeatedly recomposed in numerical form to compute the response time distribution of the overall workflow. Applicability is demonstrated on a case from the literature of composite web services, here extended in complexity to demonstrate scalability of the approach towards finer grain composition schemes, and associated with a variety of durations randomly selected from a data set in the literature of service oriented computing, so as to assess variability of accuracy and complexity of the overall approach with respect to specific timings.