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

Simple Redundant Task
Dispatch Policy

policy adopts new rules to handle such cases as
follows:

The window-size-1 is a special case of the LFPD
policy, because there is only one (1!) task-to-work
assignment. Thus, the window-size-1 LFPD
policy can be considered as an extension of the
original redundant task dispatch policy that uses
the proposed heuristics-based failure probability
estimation model. This simple redundant task
dispatch policy is used as a baseline to discuss
the effectiveness of the LFPD policy.

1. A task copy will incur a failure on a worker.
The computing power of this worker is
wasted. The greedy dispatch policy does not
dispatch such tasks that will incur failures.
A ``sleep'' message is sent to the worker.
The worker sleeps for a pre-defined period
after receiving the message.
2. A task copy will finish on a worker. Multiple
copies of this task are running on different
workers. However, this copy will finish later
than some other copies (larger estimated fin-
ish time). A task copy's estimated finish time
can be calculated when it is dispatched as:
EFT = T EPT + CurrentTime . The computing
power of this worker is also wasted, because
it does not contribute to the process of the
job. Therefore, instead of dispatching dupli-
cate task copies, the greedy dispatch policy
insures that there is only one copy of any
task. This old copy of a task is continually
replaced with a new copy that has a smaller
EFT value, whenever a new task-to-worker
assignment is found for the workers in the
dispatch window. When an old task copy
is replaced with a new one, the old copy is
canceled on the worker that executes it. If
the new task copy has a larger EFT value,
a ``sleep'' message is sent to the worker.

Greedy Dispatch Policy

The proposed LFPD policy selects a task-to-
worker assignment with the least overall failure
probability. Thus, the effectiveness of the LFPD
policy highly depends on the estimation accuracy
of the failure probabilities. If the dispatcher can
predict task failures perfectly, it can eliminate
all the task failures. In such case, an intensively
optimized dispatch policy for volunteer computing
platforms can be achieved. The comparison be-
tween such a dispatch policy and the LFPD policy
can demonstrate the effectiveness of the LFPD
policy. Therefore, in this paper, a greedy dispatch
policy that can predict failure perfectly is used
as another baseline in the following evaluation.
The greedy dispatch policy assumes that the
dispatcher knows the perfect knowledge of the
workers' future availability status. Using such
knowledge, the dispatcher can perfectly predict
whether a task can be finished on a worker without
failure. The way to find the best task-to-worker
assignment is similar to the LFPD policy. Instead
of using the assignment with the least overall
failure probability, the greedy dispatch policy uses
the assignment with the least number of failures.
Using the LFPD policy, the computing power
is wasted in some cases. These cases can be found
in advance with the knowledge of the worker's
future availability status. The greedy dispatch

The Simulator Configuration

The dispatcher and worker modules are imple-
mented with the OMNeT++ to simulate the LFPD
policy, the simple redundant task dispatch policy
(the window-size-1 LFPD policy), and the greedy
dispatch policy. To study the effectiveness of the
policies in a real world environment, two sets of
real world resource availability trace data are used
to generate the worker failures. The Skype trace
data set (Guha, 2006) has application-level re-
source availability data of 2,081 Skype supernodes