# Constructing Reliable Computing Environments on Top of Amazon EC2 Spot Instances +
## 3 Reliable Computing Environments
### Scheduling Algorithm  
To elaborate task-to-instance mappings, this work proposes MISER, a dynamic best-effort multi-workflow deadline and budget-constrained scheduling algorithm. It considers simultaneously budget and deadline constraints defined by users for concurrent workflow scheduling in heterogeneous computing systems. Algorithm 1 shows the details of MISER. The algorithm works in two main phases, namely, the task selection phase and VM instance selection phase. In the first phase (lines 2, 3, and 4), a priority, \(rank_{u}\), is assigned to each task in a ready list, \(ReadyList\). This ready list contains all the tasks whose state matches one of the following conditions: (1) a task is not running and is ready to start executing; (2) a task is running on a reclaimed SI; or (3) a task is waiting for an instance whose request was not fulfilled. The priority assigned to a task \(t_{i}\), belonging to workflow \(j\), is based on its critical path, as specified by Equation (1), where \(\overline{ET(t_{i})}\) is the average execution time of the task on available instance types offered by the cloud provider (e.g., t2.small, t2.medium, t2.xlarge, t2.2 xlarge for Amazon EC2) with different performances and prices; \(\overline{c_{is}}\) is the average communication time between tasks \(t_{i}\) and its successor \(t_{s}\) which is determined based on the average network bandwidth and latency among instance pairs. Then, a round-robin-based strategy is applied to the ready list to select a single task with the highest priority from each workflow (lines 7, 8, and 9). For a scheduling round, the round-robin loop ends when there are no more free resources to schedule tasks or the ready list is empty (i.e., all the tasks are finally scheduled). This procedure intends to avoids a high number of ready tasks causing some workflow applications to not participate in the current scheduling round. In phase two, MISER chooses the VM instance pricing model (e.g., on-demand, spot block, and unreliable SI) and type (t2.small, etc.) that better balance deadline and monetary cost QoS parameters, and provide higher reliability (lines 10, 11, and 12). Three policies apply to instance pricing model selection according to the scheduling reason: (a) a new task \(t_{i}\) can be scheduled to any instance model; (b) a task forced to migrate due to SI reliability issues can be scheduled to any already running instance or to a new on-demand instance; and (c) a task waiting for spot request fulfillment can be re-rescheduled to an on-demand instance. The rationale behind instance selection of policies (b) and (c) is that _no-capacity_ is the main reason for interruption of SIs and it has a higher impact on the fulfillment rate [14]. The instance type influences only the execution time and monetary cost. Only instances that comply with budget and deadline constraints will integrate the final set of VM candidates, \(VM_{accept}\). The budget constraint is implemented by cost policy \(CP(t_{i},j)\) as defined by Equation (2), and is determined based on two factors: (a) \(Cost_{min}(t_{i},j)\), the minimum execution cost of task \(t_{i}\), belonging to workflow \(j\), among available instance candidates; and (b) \(\Delta_{Cost}(j)\), the spare budget which is determined as the difference between remaining budget at a scheduling round, and the cheapest monetary cost assignment for unscheduled tasks belonging to workflow \(j\).