# Constructing Reliable Computing Environments on Top of Amazon EC2 Spot Instances +
## 3 Reliable Computing Environments
### Scheduling Algorithm
```
1:procedure MISER (\(ReadyList\))
2:for\(t_{i,j}\in ReadyList\)do
3:\(rank_{u}(t_{i},j)\)\(\triangleright\) A priority is assigned to each task based on Equation (1)
4:endfor
5:\(VM_{free}\leftarrow\) free resources
6:\(c\gets 0\)\(\triangleright\)\(c\) is necessary for round-robin strategy in line 8
7:while\(ReadyList.size>0\) & \(VM_{free}>0\)do
8:\(j\leftarrow\) next workflow \(MOD\)\(c\)++\(\triangleright\) Round-robin to select the next workflow
9:\(t_{i}\leftarrow\) task of workflow \(j\) with highest \(rank_{u}\)\(\triangleright\) Gets task with highest priority
10:\(VM_{accept}\leftarrow\) instance model policy \(\cap\)\(VM_{free}\)\(\triangleright\) Choose instances assuring sched. policy
11:\(VM_{accept}\gets CP\cap VM_{accept}\)\(\triangleright\) Instances must follow cost policy in Equation (2)
12:\(VM_{accept}\gets DP\cap VM_{accept}\)\(\triangleright\) Instances must follow deadline policy in Equation (3)
13:for\(VM_{k}\in VM_{accept}\)do
14: find quality measure \(Q(t_{i},VM_{k})\)\(\triangleright\) For each instance determine Q in Equation (7)
15:endfor
16:\(VM_{sel}\leftarrow\) instance \(VM_{k}\) with highest \(Q\)
17: assign task \(t_{i}\) to \(VM_{sel}\)
18: update \(\Delta_{Cost}(j)\)
19:\(VM_{free}\gets VM_{free}-VM_{sel}\)
20: remove task \(t_{i}\) from \(ReadyList\)
21:endwhile
22:endprocedure
```  
**Algorithm 1** MISER scheduling algorithm. \[CP(t_{i},j)=Cost_{min}(t_{i},j)+\Delta_{Cost}(j) \tag{2}\]  
In turn, the deadline constraint is implemented by deadline policy \(DP(t_{i},j)\). Based on the workflow application deadline, \(DP(t_{i},j)\) assigns a sub-deadline to task \(t_{i}\), which is computed recursively by traversing the task graph upwards, starting from the exit task. Equation (3) shows that the sub-deadline depends on the \(ET_{min}(t_{s})\), the minimum execution time of task \(t_{s}\), the successor of \(t_{i}\), among available instances. \(DP(t_{s},j)\) is the sub-deadline of \(t_{s}\), \(\overline{c_{i,s}}\) is the average communication time between tasks \(t_{i}\) and its successor \(t_{s}\), and \(MT_{max}(t_{i})\) is the maximum migration time for \(t_{i}\) among available instances. The Bernoulli parameter \(\Theta(t_{i})\) ensures migration time accounting for whether SIs are allowed by the system scheduling policy. The workflow application deadline defines the sub-deadline of the exit task. The rationale behind the minimum execution time relates to the possibility of reducing execution costs, since expanding the sub-deadline assigned to task \(t_{i}\) allows the scheduler to exploit idle slots between two already scheduled tasks on a VM instance, as long as precedence constraints are preserved. Actually, this is the policy applied by the well known HEFT scheduling algorithm [42]. \[ \begin{split} DP(t_{i},j)=\min_{\forall t_{s}\in succ(t_{i})} \left(DP(t_{s},j)-\overline{c_{i,s}}-ET_{min}(t_{s})\right)-MT_{max}(t_{i}) \times\Theta(t_{i}),\\ \Theta(t_{i})=\begin{cases}1,&\text{if $t_{i}$ can be scheduled on SIs}\\ 0,&\text{otherwise}\end{cases}\end{split}  \tag{3}\]  
The next step consists of selecting \(VM_{sel}\), that is, the best VM instance to run \(t_{i}\) from the set of acceptable VM candidates \(VM_{accept}\) (lines 13, 14, and 15). Three relative quantities are defined, namely, time quality \(T_{Q}\), monetary cost quality \(C_{Q}\), and reliability quality \(R_{Q}\) for task \(t_{i}\) on each acceptable instance \(VM_{k}\in VM_{accept}\). Equations (4)-(6) define \(T_{Q}\), \(C_{Q}\), and \(R_{Q}\), respectively. In order to make the value of each relative quantity fall into the \([0,1]\) interval, \(T_{Q}\), \(C_{Q}\) are normalized. Since \(R_{Q}\) is calculated as the difference between the unity and a cumulative distribution function, the result naturally falls within \([0,1]\) interval.