Adaptive Control of Redundant Task Execution for Dependable Volunteer Computing - Cloud, Grid and High Performance Computing: Emerging Applications - page 148

ing total process time of the simple redundant
task dispatch policy.
Figure 4 shows how the normalized total
process time changes with the dispatch windows
size and the mean task process time, using the
Skype trace data set. The results with Microsoft
PCs trace data set are shown in Figure 5.

both the two tasks. This EFP increment makes
the overall failure probability ( OFP ) of both two
possible assignments higher. The LFPD policy
is designed to reduce the number of failures, by
finding proper task-to-worker assignments. How-
ever, if all the assignments provide a high overall
failure probability, the LFPD policy becomes less
efficient. As a result, the LFPD policy delivers
less improvement in the case of a larger mean task
process time. In both of these two trace data sets,
the mean TTF is 55125 seconds. The large mean
task process time (10000 seconds) enlarges the
tasks failure probability. Thus, the LFPD dispatch
is less efficient, compared to the ones with a small
mean task process time.
The results with two trace data sets are slightly
different for their different availability character-
istics. It is because of an overhead introduced by
the dispatch window. When the dispatch window
is not full, the workers that are waiting in the win-
dow are idle. Their computing power is wasted.
Thus, the less time to fill a dispatch window, the
better performance can be achieved. In the case of
these two trace data sets, the average number of
online workers in the Microsoft PCs trace is much
larger. Thus the time of the Microsoft PCs trace
data set to fill a dispatch window can be expected
to be much shorter than that of the Skype data
set. Therefore, the LFPD policy delivers a better
performance improvement with the Microsoft PCs
trace data set for all the parameter combinations.

Comparison with the Simple
Redundant Task Dispatch Policy

The results indicate that the LFPD policy outper-
forms the simple redundant task dispatch policy
(window-size-1 LFPD). The improvement is more
significant for a larger number of task groups. A
smaller mean task process time also leads to a
slightly better improvement. For 20 task groups
and the mean task process time of 1250 seconds,
LFPD delivers up to 6% and 12% improvements
for the Skype trace data set and Microsoft PCs
trace data set, respectively.
The number of task groups is related to how
many times a workflow is blocked during the
process of the workflow. The ``blocked'' status
introduces a serious performance overhead, be-
cause the computing power is used for re-execution
of the failed tasks. The LFPD policy reduces the
number of task failures, and thus mitigates this
performance overhead. It explains the reason why
the LFPD policy is more efficient for a larger
number of task groups.
For a given trace data set, a larger mean task
process time leaves less rooms for the LFPD
dispatch to find a better assignment. As shown
in Equation (4), the EFP of any task-to-worker
assignment depends on the task process time, the
current time, and the start time of the worker. Be-
cause the latter two values are given while finding
a better task assignment, the EFP is decided only
by the task process time. For example, there are two
workers in the dispatch window, and two selected
tasks. Given any assignment, a larger mean task
process time leads to a longer task process time
on both workers. Therefore, the EFP increases for

Comparison with the
Greedy Dispatch

As shown in both Figures 4 and 5, the greedy
dispatch policy beats the LFPD policy for a large
mean task process time (10000 seconds). The rea-
son is that the greedy dispatch policy eliminates
all the task failures with its perfect knowledge
of the worker availability status. While both the
simple redundant task dispatch policy and the
LFPD policy suffer from the inefficiency for the
high failure probabilities, the performance of the