Information Technology Reference
In-Depth Information
sabotage to the computation. It is reported in [27] that a large fraction of participants (about
35 %) actually returned at least one erroneous result in a real VC.
Against the sabotaging, some sabotage-tolerance mechanisms are proposed for reliable
computation. However, (i) the sabotage tolerant performance and the drawbacks of those
mechanisms have been hidden in real VC systems since they are proposed and evaluated
based on unrealistic VC models; (ii) There is no dynamic scheduling method although the
sabotage-tolerance performance is closely related to job scheduling in that redundant jobs
for sabotage-tolerance are allocated to volunteers in a job scheduling procedure. Therefore,
major VC frameworks still provide the simplest sabotage-tolerance mechanism based on a
static job scheduling, which significantly degrades the performance instead of ensuring the
reliability of computation.
To solve this problem, we propose a dynamic job scheduling method for sabotage-
tolerance mechanisms and evaluate it based on practical VC model which considers work-
ers' dynamic activities. The key idea is to introduce novel metrics, i.e. expected-credibility
and the expected number of results, for dynamic job scheduling. These metrics take account
of active (running) jobs and show actual condition of redundant computation, which works
to avoid excess job executions and performance degradation. Different from the static round
robin method used in [23], the proposed method selects a proper job dynamically based on
these metrics.
The remainder of this chapter is organized as follows: Section 2 provides some back-
ground knowledge of VCs and describes the basic and more practical VC models. Section 3
introduces existing sabotage-tolerance mechanisms and compares their performance in VC
models described in Section 2. Section 4 proposes a dynamic job scheduling method for
sabotage-tolerance mechanisms and demonstrates the performance. Section 5 concludes
this chapter with a summary and an indication of our future work direction.
2.
VC Platform
In this section, we will provide some background knowledge of VCs which will help to
understand the main body of this chapter. We will first introduce major VC projects which
have run successfully or is currently running on the Internet (Sec. 2.1), and the remaining
sections cover VC framework (Sec. 2.2), VC model (Sec. 2.3), and existing problem and
motivation of this chapter (Sec. 2.4).
2.1.
VC Projects
Large scale VC projects began in the 1990's with The Great Internet Mersenne Prime Search
(GIMPS) [13] and Distributed.net [14]. These projects allow people to solve many paral-
lel problems that were previously computationally infeasible. The application areas of VC
include medicine, science, chemistry, and mathematics. More than 20 VC projects are
currently running, including the well-known SETI@home project, which searches for evi-
dence of extraterrestrial life [11, 12]. The purpose of these projects are searching for cures
for diseases, looking for evidence of extraterrestrial intelligence, finding Mersenne prime
numbers, and so on. Below is the list of some famous VC projects.
