# Workflow Trace Profiling and Execution Time Analysis in Quantitative Verification
## 7 Related Work  
Workflow execution time analysis is heavily investigated in the existing works, most of which belong to a specific problem domain, such as the _makespan estimation for workflow scheduling_ and the _QoS aggregation in service composition_ (i.e., how to aggregate QoS metrics, such as execution times, for composite services from those of atomic services). Many works in those two domains represent makespans and QoS metrics as constant values (e.g., [30; 31; 32; 33; 34]). We discuss only those works in which the makespans and QoS metrics are modelled as stochastic values, as those analytic methods are more related to our approach. In the framework proposed by [PERSON] et al. [22], the QoS metrics of atomic services are modelled as independent discrete random variables. Their algorithm works recursively to derive the Probability Mass Functions (PMFs) for the service QoS metrics through five common composition structures (i.e., sequential, conditional, loop, synchronised parallel and unsynchronised parallel) until the PMF of the end-to-end QoS is computed. Although the PMF composition is straightforward, in order to represent the empirical QoS values accurately, the support of the PMF must consist of a high number of small discretised value ranges. The complexity of their algorithm grows exponentially as the support size of the PMF increases. [PERSON] et al. [24] presented an approach to aggregate the continuously  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline \multirow{2}{*}{\# **State in SMC**} & \multirow{2}{*}{\# **Location in DFA**} & \multicolumn{4}{c}{**Time (ms)**} \\ \cline{3-6}  & & **1 st mo. ** & **2 nd mo. ** & **3 rd mo. ** & **4 rd mo. ** \\ \hline
119 & 30 & 7 & 11 & 15 & 19 \\
199 & 50 & 15 & 19 & 25 & 31 \\
399 & 100 & 58 & 70 & 85 & 101 \\
799 & 200 & 162 & 196 & 238 & 282 \\
1599 & 400 & 69  
distributed QoS metrics of service components in the same aforementioned five composition patterns. In order to compute the composite QoS, they assumed that the distributions of all QoS metrics must have the same form, and that the histograms must have the same start point and width of intervals. This assumption may be over restricted in application. [PERSON] et al. [23] employed an SMC to formally model composite services. They derived basic statistical parameters (i.e., means and variances) of QoS metrics (i.e., the response time and availability probability) for composite services in the closed form of the basic statistical parameters for atomic services. Although we also use an SMC as the formal model, our method computes not only the first and second moments but also high-order moments numerically, which are not so convenient to express in a closed form. Our approach is also equipped with an expressive formalism (i.e., DFA) to specify trace components for quantitative verification. In the task scheduling framework of workflows proposed by [PERSON] et al. [18], an essential component is a method to infer the execution time of workflows from generally (and independently) distributed times of basic tasks. Their method estimates both the CDFs and characteristic functions (CFs) of task times. By representing the workflow as a directed acyclic graph (DAG) (without loops), they can employ the former to aggregate the parallel structure and later to aggregate the sequential structure and branching structure. During the aggregation process, their method uses Fourier transforms between CDFs and CFs at the cost of some approximation error. In contrast, by considering the last-completed parallel threads for execution time analysis purposes, our approach reduces to the parallel structure into the branching structure and works on the computation of moments with loops. Moreover, the moment estimation of task times from workflow execution data is much easier than the estimation of CDFs and CFs. [PERSON] et al. [17] proposed a probabilistic model to estimate the workflow makespans for scientific grid applications.