# Workflow Trace Profiling and Execution Time Analysis in Quantitative Verification
## 4 Model Building
### Workflow Execution Summary  
An execution trace of a workflow \(\mathcal{W}\) is a list of events with the following fields: (eventType, timestamp), where eventType is an event type, such as entering a stage in the workflow, and timestamp is the event timestamp. The list may also contain a unique ID to identify the execution instance. Execution traces include all the information to create a workflow execution (data) summary.  
Assume that we have collected a set of execution traces falling into a prescribed time window. We remove the events that do not belong to last-completed threads. With the execution trace data, we can replay the executions and calculate two kinds of statistical values. The first kind of statistical values are the _frequencies_ of transitions, denoted \(\mathtt{Freq}(w,w^{\prime})\), where \(w\longrightarrow w^{\prime}\) is a transition in \(\mathcal{W}\). The frequencies can be calculated by counting the pairs of consecutive events. The second kind of statistical values are _power sums_ of transition time intervals, denoted \(\mathtt{PSum}(j,w,w^{\prime})\), where \(j\) is a power, and \(w\longrightarrow w^{\prime}\) is a transition in \(\mathcal{W}\). Let \(t\) and \(t^{\prime}\) be the timestamps of two consecutive events that correspond to \(w\) and \(w^{\prime}\), respectively, and let \(\Delta=t^{\prime}-t\). Thus, we have a set of time intervals \(\{\Delta_{1},\ldots,\Delta_{m}\}\) for \(w\longrightarrow w^{\prime}\), where \(m=\mathtt{Freq}(w,w^{\prime})\). Then, we calculate \(\mathtt{PSum}(j,w,w^{\prime})=\sum_{i=1}^{m}\Delta_{i}^{j}\), where \(1\leq j\leq k\). An alternative way of interpreting time intervals of transitions is the _holding time at state \(w\) if the next state is \(w^{\prime}\)_. For example, when the execution of SimpleFlow is located in \(w_{1}\) in \(\mathcal{W}_{SF}\), the transition time from \(w_{1}\) to \(w_{3}\) means the task time for Task1.  
The pair \(\mathtt{Summ}=(\mathtt{Freq},\mathtt{PSum})\) is an execution summary of the workflow. It is noteworthy that one important property of \(\mathtt{Summ}\) is _mergeability_[25; 26]: Given \(\mathtt{Freq}_{1}\) and \(\mathtt{Freq}_{2}\) (resp., \(\mathtt{PSum}_{1}\) and \(\mathtt{PSum}_{2}\)), we can simply merge them, namely, let \(\mathtt{Summ}_{1}+\mathtt{Summ}_{2}=(\mathtt{Freq}_{1}+\mathtt{Freq}_{2}, \mathtt{PSum}_{1}+\mathtt{PSum}_{2})\). This property enables the parallel calculation of \(\mathtt{Summ}\) in practice. Moreover, we can calculate the summary \(\mathtt{Summ}\) with sliding or decaying windows [4]. Assume that we calculate \(\mathtt{Summ}_{\text{old}}\) with historical data (e.g., data from the past week) and \(\mathtt{Summ}_{\text{new}}\) with recent data (e.g. data from the past hour). In the case of (exponential) decaying windows, we can let \(\mathtt{Summ}=\lambda\mathtt{Summ}_{\text{old}}+\mathtt{Summ}_{\text{new}}\), where \(\lambda\in[0,1]\) is a decaying factor. Thus, we represent the entire execution history with a compact summary \(\mathtt{Summ}\).  
We use a _(statistical) workflow profile_ to refer to the combination of a workflow model \(\mathcal{W}\) and its execution summary \(\mathtt{Summ}\), where \(\mathcal{W}\) is fixed, and \(\mathtt{Summ}\) is updated by the aforementioned method as more recent execution trace data are collected.