Access Restriction

Author Araujo, Filipe ♦ Domingues, Patricio ♦ Kondo, Derrick ♦ Silva, Luis Moura
Source CiteSeerX
Content type Text
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword High Error Rate ♦ Intermediate Checkpoint ♦ Desktop Grid Result ♦ Result Validation ♦ Error Rate ♦ Correct Replica ♦ Replicated Computation ♦ Erroneous Computation ♦ Error Detection ♦ Theoretical Analysis ♦ Simulation Experiment ♦ Volunteer Desktop Grid ♦ Immediate Replacement ♦ Task Execution ♦ Intermediate Checkpointing ♦ Useful Execution ♦ Intermediate Execution Point ♦ Simulation Result ♦ Checkpoint Frequency ♦ Computational Error
Description We present a scheme based on the comparison of intermediate checkpoints that accelerates the detection of computing errors of bag-of-tasks executed on volunteer desktop grids. Currently, in the state-of-the-art, replicated task execution is used for result validation. Our method also uses replication, but instead of only comparing results at the end of the replicated computations, we validate ongoing executions by comparing checkpoints of their intermediate execution points. This scheme significantly reduces the time to detect a computational error, which we show with both theoretical analysis and simulation results. In particular, we develop a model that gives the benefit of intermediate checkpointing as a function of checkpoint frequency and error rate, and we confirm this model with simulation experiments. We find that with an error rate of 5 % and checkpoint frequency of 20 times per task, the gain is as high as 35 % compared to the case where error detection is done only at the end of task execution; for higher checkpoint frequencies or high error rates, the benefits are even greater. In addition, when an erroneous computation is detected at an intermediate execution point, we propose the immediate replacement of that computation with a correct replica from another worker. In this way, useful execution and further validation can continue from that point onward instead
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2006-01-01