# Constructing Reliable Computing Environments on Top of Amazon EC2 Spot Instances +
## 3 Reliable Computing Environments
### Scheduling Algorithm
\[T_{Q}(t_{i},j,VM_{k})=1-\frac{FT(t_{i},j,VM_{k})-FT_{min}(t_{i},j)}{ FT_{max}(t_{i},j)-FT_{min}(t_{i},j)} \tag{4}\]  
where \(FT(t_{i},j,VM_{k})\) represents the finish time for task \(t_{i}\) running on \(VM_{k}\) instance, and \(FT_{max}(t_{i},j)\) and \(FT_{min}(t_{i},j)\) are the maximum and minimum execution times determined among all available instance types and pricing models, respectively. \(T_{Q}\) reaches the unity for a VM instance providing the minimum execution time. \[C_{Q}(t_{i},j,VM_{k})=1-\frac{Cost(t_{i},j,VM_{k})-Cost_{min}(t_{i},j)}{Cost_{ max}(t_{i},j)-Cost_{min}(t_{i},j)} \tag{5}\]  
where \(Cost(t_{i},j,VM_{k})\) is the monetary cost of executing task \(t_{i}\) on \(VM_{k}\) instance, and \(Cost_{max}(t_{i},j)\) and \(Cost_{min}(t_{i},j)\) are the maximum and minimum monetary costs determined among all available instance types and pricing models, respectively. \(C_{Q}\) reaches unity for the cheapest VM instance. Instance pricing models present different reliability. While on-demand instances remain active until they are terminated by the client, spot block instances will not be terminated within a specified duration of 1-6 h. On the contrary, SIs can be reclaimed by EC2 at any time. Reliability quality equals the unity for on-demand and spot block instances. For SIs, reliability quality is probabilistically determined based on the cumulative distribution function. Equation (6) shows the reliability quality \(R_{Q}(t_{i},j,VM_{k})\) for an instance \(VM_{k}\), where \(\chi(t_{i},j,VM_{k})\) is: (a) zero for on-demand or spot block instances, or (b) the cumulative distribution function \(CDF_{logn}\) (\(\mu\) is the mean and \(\sigma\) is the standard deviation). \(CDF_{logn}\) tends to the unity as \(FT(t_{i},j,VM_{k})\) distantates from SI requesting time. The rationale is to favor selection of fresh SIs over long-running ones, in order to probabilistically avoid failure and to balance monetary cost and reliability since SIs are cheaper yet less reliable. In this work, we used the log-normal probability distribution because the curve fitted well with the data provided by recent studies on performance and behavior characterization of Amazon EC2 SIs [14]. In a real usage scenario, \(\mu\) and \(\sigma\) can be adjusted online based on historical data. \[R_{Q}(t_{i},j,VM_{k})=1-\chi(t_{i},j,VM_{k}),\] \[\text{where }\chi(t_{i},j,VM_{k})= \begin{cases}CDF_{logn}(FT(t_{i},j, VM_{k}),\mu,\sigma),\text{ if }VM_{k}\text{ is SI}\\ 0,\quad\text{otherwise}\end{cases}  \tag{6}\]  
The multi-objective utility function \(Q\), defined by Equation (7), combines the three objectives \(T_{Q}\), \(C_{Q}\), and \(R_{Q}\). By definition, utility functions not only smoothly express the degree of preference under different values for each objective, but also normalize the ranges of all the objectives into the same interval \([0,1]\). Therefore, \(Q\) is used to obtain the best balance between time, monetary cost, and reliability. \[Q(t_{i},j,VM_{k})=T_{Q}(t_{i},j,VM_{k})+C_{Q}(t_{j},j,VM_{k})+R_{Q}(t_{i},j, VM_{k}) \tag{7}\]  
The algorithm selects the instance model and type \(VM_{sel}\) that provides the highest quality measure \(Q\) to run task \(t_{i}\) (lines 13, 14, and 15). MISER is combined with a monitoring mechanism that is responsible for checking the waiting time to fulfill spot requests (i.e., characteristic that affects spot block and SIs), and for handling notification events regarding SI interruptions. As stated by Algorithm 2, MISER algorithm (i.e., Algorithm 1) will be invoked in a new scheduling iteration when an event occurs.