内容总结：
之前工作流调度算法很少考虑容错，他们的目的多为减少完成时间和开销，满足规定预算和时间约束，增加可靠性。考虑了容错不可避免就会增加时间和成本。解决容错问题使用重新提交技术可能会导致不可接受的执行时间增加，并可能违反截止日期，而复制方法会增加执行成本。
本文提出了一种时间和成本开销接近最优的容错工作流调度算法。首先，作者假设了一个具有不确定任务参数的工作流随机模型（工作流通常建模为有向无环图(DAG)，节点代表工作流任务，边代表其中的优先约束），并使用区间算法对任务执行时间进行建模，提出了一种新的调度算法，其中任务分配决策是根据计算资源的可执行性波动来进行的（以往的静态调度没有考虑资源的可用性）。其次，作者采用了重新提交和复制技术的有效组合来实现两者的优势，并提出了一种算法来可靠地调度科学工作流，同时具有接近最佳的额外时间和成本。所提出的方法实现了可靠性的显著提高，而额外的执行时间和成本几乎可以忽略不计。
涉及概念知识：
注：1.工作流任务的两种冗余方案:复制冗余，重提交冗余；复制冗余需要更少的计算时间，但成本更高，而重新提交冗余需要更少的预算，代价是更高的完工时间。
2.任务的关键程度是一种度量，它表明我们对任务是否处于关键路径上的确定程度。一旦确定了任务的关键程度，就可以为该任务确定适当的冗余方案。
3.资源的处理能力和链路的传输能力分别用MIPS和Mbps来指定。
4.资源失效之间的时间被建模为具有威布尔分布的随机变量。
本文作者提出了一种方法来有效的组合两种冗余方案，以实现两者优势互补，选择冗余方案是根据实际情况选择的。以往的任务的关键程度级别，指示在不延迟工作流终止的情况下，可以延迟多少任务执行，关键程度取决于他是否在关键路径上。本文定义了一种新的关键程度衡量标准为每个任务分配关键程度。
以前的工作流调度方法中，通常的假设是任务执行时间和数据传输时间是固定和已知的。由于循环和决策结构的不确定性以及计算资源的可用处理能力，这些量既不是固定的，也不是已知的。在本文中任务的执行时间和数据传输时间被定义为随机变量，由于这些不确定性，任务的关键程度也不确定因此，为了能够使用经典的关键路径算法，作者计算了具有间隔任务执行时间的原始随机工作流的三个间隔近似。作者扩展了经典的关键路径算法来处理区间工作流。我们使用区间数学来获得作为区间数的区间工作流中任务的滞后。
任务的大小(用百万条指令表示)和输出数据的大小(用位表示)是正态分布的随机变量，其均值和标准差是根据历史数据确定的因此执行时间和数据传输时间也是非确定性的，并且遵循正态分布。
公式引入：
任务ti大小的平均值 任务ti大小的标准差
APC(Rj)表示资源Rj的可用处理能力
ti输出任务转移说需要时间的均值 ti输出任务转移说需要时间的标准差
Ws：随机工作流 工作流任务服从正态分布 它的三个区间近似值
ti的执行时间和数据传输数据计算如下:
任务ti的执行时间和任务数据传输时间之和由：
最早开始时间和最早完成时间如下：
pred(ti)为ti的前置任务集合
一个任务的最早开始时间是它的每个前置任务的EST(tj)之和加上该任务的执行时间和数据转换时间的最大值
最晚开始时间和最晚完成时间如下：
succ(ti) 为ti的后续集
每个任务的延迟：
任务ti的关键程度
1.输入一组随机工作流Ws 2.将任务ti的关键程度值为0 3.在k=0到k=2做循环： 计算区间工作流W1（k） 计算ti在w1（k）的滞后区间 当uet（ti）大于滞后区间的下限： 关键等级+0.5 当大于滞后区间的上限： 关键等级+0.5 4.返回关键等级
Available Processing Capacity可用处理能力：
我们使用一种方法，通过估计执行工作流任务的资源上每个处理元素的可用处理能力来比较资源的处理能力
该基准的估算依据：
n：表示资源正在处理的任务数包括要分配的新任务
m： 处理原件数量
：每个处理原件的处理能力
：处理本地工作负载所消耗的处理器时间部分。
可用处理能力估计如下：
Fault-Tolerance Scheme Selection容错方案选择：
我们提出了一种冗余选择方法：容错机制是根据选择的，如果它小于3我们使用重提交冗余否则使用复制。如果选重提交成功完成任务之前提交任务的预期次数是带有参数的几何随机变量的期望值pi（是ti在每次提交过程中成功的概率）计算pi的值是ti资源的上次修复时间和执行时间，如果ti用重提交成功终止之前所需提交的平均数量为1/pi；如果选择复制：ti的副本数量 复制次数是并行组合成功终止的概率（高于给定的阈值θ），N是复制副本的最小数量。由于资源故障概率越来越高 成功提交的概率pi在提交试验中，随着时间的推移而减少。
The Algorithm：
算法解析：
在就绪队列更新时： 1.让Ws成为随机工作流的剩余部分 2.在k=0-2进行循环： 为每个就绪任务ti计算区间工作流W1（k） 用之前的计算关键程度算法计算ti的关键等级 根据容错方案选择选择容错类型 将任务提交给适当的资源（根据4.2.3） 在任务执行失败时，请执行以下操作: 1.将ti设置为失败任务 2.如果没有ti的副本正在处理： 重新调度ti 3.如果发生定时故障： 终止工作流中的剩余任务 在任务完成时，请执行以下操作: 1.让任务ti设置为完成任务 2.让ti标准为已经完成 3.如果有ti的副本正在进行： 取消所有副本任务 4.如果ti是正在完成任务： 标记工作流为已完成 否则： 对于每个属于succ（ti）的任务tj，如果被标记为已完成 在准备队列中添加tj
