![](https://csdnimg.cn/release/download_crawler_static/15387431/bg4.jpg)
RU ¼
X
n
i¼1
ðRU
comp
ðt
i
ÞþRU
comm
ðt
i
ÞÞ
Notations are listed in Table 1. We address the problem of finding a schedule S that minimizes the resource usage (i.e., RU),
while satisfying a prespecified reliability requirement.
3. Reliability analysis
In this section, we analyze the reliability of a schedule, and present the upper bound and lower bound.
3.1. The upper bound
Suppose the reliability attained by scheduling a replica of t
i
on P
j
is rel
j
i
, then rel
j
i
is comprised of the computation and
communication reliability: rel
j
i
¼ prel
j
i
Q
t
x
2Parðt
i
Þ;k2Pathðt
x
;jÞ
crel
k
e
x;i
, where prel
j
i
indicates the computation reliability and crel
k
e
x;i
is the communication reliability provided by link k. In case of an entry task t
i
without parents, rel
j
i
¼ prel
j
i
.
Theorem 1. Given a schedule S, the reliability of the schedule S follows that: RelðSÞ 6
Q
n
i¼1
1
Q
rel
j
i
2REL
i
1 rel
j
i
, where the
equation is established iff jPREP
k
j 6 1, for
8
k 6 m.
Proof. The proof strategy is, first, to show that the equation is established for the schedule S
max
, where
8
k 6 m; jPREP
k
j 6 1by
Lemma 1. Then Lemma 2 shows that the reliability of S, which is constructed by ‘‘moving’’ the replicas from S
max
is less than
RelðS
max
Þ.
Lemma 1. If in the schedule S
max
;
8
k 6 m; jPREP
k
j 6 1, then the reliability of S
max
is equal to
Q
n
i¼1
1
Q
rel
j
i
2REL
i
1 rel
j
i
.
Proof. This is quite straightforward because if
8
k 6 m; jPREP
k
j 6 1, each processor is assigned with at most one replica, then
the failure on a single replica does not affect the other replicas’ execution. Therefore, the reliability of schedule S
max
is equal
to the probability that at least one replica of each task succeeds. h
Suppose there is a ‘‘move’’ operation that manually moves a replica from one processor with no other replicas to one with
only some replicas of his predecessors, and suppose the ‘‘move’’ operation does not affect the reliability of the replica itself
(rel
j
i
). Then any given schedule S could be obtained by continuously moving the replicas from S
max
. The next, we prove that
this ‘‘move’’ operation continuously decreases the reliability.
Lemma 2. Give a schedule S
1
, where a replica rep
k
i
is the only replica placed on processor k. If we modify S
1
into S
2
by moving rep
k
i
to a processor u, which has been assigned with some replicas of his predecessors, but not having a replica of task i. Then the
reliability provided by the schedule S
2
is less than S
1
: RelðS
2
Þ < RelðS
1
Þ.
Proof. Define PFI (Possible failure intersections) as a set of any arbitrary intersections of failures, thus
PFIðSÞjj¼
Q
m
k¼1
PREP
k
jjþ1ðÞ.
Table 1
List of notations.
Notations Definition
Job
Workflow, Job ¼ft
1
; t
2
; ...; t
n
g.
Pro Processors set, Pro ¼fP
1
; P
2
; ...; P
m
g.
S Schedule generated by any algorithms.
RelðSÞ
Reliability of schedule S.
rep
j
i
A replica of task t
i
scheduled on processor P
j
.
REP
i
Replicas of task t
i
; REP
i
¼frep
j
i
; rep
k
i
; ...; rep
u
i
g.
REP All replicas, REP ¼fREP
1
; REP
2
; ...; REP
n
g.
PREP
k
Replicas on P
k
; PREP
k
¼frep
k
1
; rep
k
2
; ...; rep
k
n
g.
prel
j
i
Reliability provided by processor j for replica rep
j
i
.
crel
k
e
ij
Reliability provided by link k for communication e
ij
.
rel
j
i
Reliability provided by the system for replica rep
j
i
.
REL
i
REL
i
¼frel
j
i
; rel
k
i
; ...; rel
u
i
g.
Parðt
i
Þ Parent tasks of task t
i
.
Chdðt
i
Þ
Children tasks of task t
i
.
570 L. Zhao et al. / Parallel Computing 39 (2013) 567–585