## 3 System Model
### Scientific Workflow Application Model  
The standard way to represent a BoT-based workflow is a Directed Acyclic Graph (DAG) \(W=(V,E,B)\) in which \(V=\{v_{1},v_{2},\ldots,v_{n}\}\) is the set of vertices representing \(n\) different tasks of the workflow, \(E=\{e_{ij}|(1\leq i\leq n,1\leq j\leq n,i\
eq j\}\) is the set of directed edges between the \begin{table}
\begin{tabular}{l l} \hline \hline
**Notation** & **Description** \\ \hline \(W\) & Workflow represented by Directed Acyclic Graph (DAG) \\ \(V\) & Set of tasks of the workflow, represented by vertices of the DAG \\ \(E\) & Set of directed edges between the vertices \\ \(BoT\) & Set of BoTs \\ \(VM\) & Set of Virtual Machines (VMs) \\ \(n\) & Number of tasks \\ \(k\) & Number of VM types \\ \(u\) & Number of BoTs \\ \(v_{i}\) & A task such that \(v_{i}\in V\) \\ \(v_{j}\) & A task such that \(v_{j}\in V\) \\ \(v_{entry}\) & Virtual entry node \\ \(v_{exit}\) & Virtual exit node \\ \(v_{run}\) & Running task \\ \(e_{ij}\) & An edge such that \(e_{ij}\in E\) between the tasks \(v_{i}\) and \(v_{j}\) \\ \(e_{p,i}\) & Inward edges of task \(v_{i}\) \\ \(e_{i,c}\) & Outward edges of task \(v_{i}\) \\ \(bot_{q}\) & A BoT such that \(bot_{q}\in Bot\) \\ \(m_{r}\) & A virtual machine of type \(r\) such that \(m_{r}\in VM\) \\ \(pred(v_{i})\) & Immediate predecessor of task \(v_{i}\) \\ \(succ(v_{i})\) & Immediate successor of task \(v_{i}\) \\ \(RT^{r}_{i}\) & Estimated Runtime of task \(v_{i}\) on VM \(m_{r}\) \\ \(CT^{r}_{ij}\) & Communication time of edge \(e_{ij}\) from tasks \(v_{i}\) and \(v_{j}\) on a VM \(m_{r}\) \\ \(ET^{r}_{i}\) & Execution time of task \(v_{i}\) on VM \(m_{r}\) \\ \(ST^{r}_{i}\) & Start time of task \(v_{i}\) on VM \(m_{r}\) \\ \(FT^{r}_{i}\) & Finish time of task \(v_{i}\) on VM \(m_{r}\) \\ \(EC^{r}_{i}\) & Execution cost of task \(v_{i}\) on VM \(m_{r}\) \\ \(l_{i}\) & Service length of task \(v_{i}\) \\ \(p_{r}\) & Processing power of VM \(m_{r}\) \\ \(h_{r}\) & Billing interval length of VM type \(m_{r}\) \\ \(c_{r}\) & Cost per interval unit of VM type \(m_{r}\) \\ \(b_{r}\) & Bandwidth capacity of VM \(m_{r}\) \\ \(d_{r}\) & Provisioning delay in VM allocation \\ \(pv_{r}\) & VM performance variability \\ \(slt_{r}\) & Start leasing time of VM \(m_{r}\) \\ \(tc_{ij}\) & Data transfer cost of communicating data from task \(v_{i}\) to \(v_{j}\) \\ \(s_{ij}\) & Size of data needed to be communicated from task \(v_{i}\) and \(v_{j}\) \\ \(urank_{i}\) & Upward rank of a task \\ \(dd_{i}\) & Degree of dependency of task \(v_{i}\) \\ \(lv\Big{(}v_{j}\Big{)}\) & Maximum number of edges from task \(v_{entry}\) to \(v_{j}\) \\ \(count_{lv}\) & Number of tasks in the level \(lv\) \\ \(DL_{W}\) & Deadline associated with the workflow \(W\) to complete its execution \\ \(MP_{W}\) & Overall schedule length of workflow \(W\) \\ \(AS_{W}\) & Elapsed time between \(DL_{W}\) and the estimated \(MP_{W}\) \\ \(AS_{lv}\) & Available spare time of a level \(lv\) \\ \(AS_{i}\) & Available spare time of a task level \(v_{i}\) \\ \(SD_{i}\) & Estimated sub-deadline for task \(v_{i}\) of the workflow \\ \(ET^{r}_{i}\) & Earliest finish time of task \(v_{i}\) on VM \(m_{r}\) \\ \(CPT^{sel}\) & Cumulative processing time of submitted tasks on VM \(m_{sd}\) \\ \(y_{r,u}\) & Variable representing number of tasks assigned to \(u^{th}\) VM of type \(r\) \\ \(n^{r}_{bot}\) & Number of tasks in \(bot\in BoT\) assigned to VM of type \(r\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Notations. vertices, representing data or control dependencies between the tasks \(v_{i}\) and \(v_{j}\), indicating a task \(v_{j}\) cannot start its execution before \(v_{i}\) finishes and sends all the needed output data to task \(v_{j}\) and \(BoT=\{bot_{1},bot_{2},\dots,bot_{u}\}\) is the set of BoTs, in which \(bot_{q}\) is the set of \(q^{th}\) BoT. Each task has an estimated runtime \(RT_{i}\) which denotes the precedence constraint assigned to task \(v_{i}\).