Information Technology Reference
In-Depth Information
Chapter 7
S
ABOTAGE
-
TOLERANT
J
OB
S
CHEDULING FOR
R
ELIABLE
V
OLUNTEER
C
OMPUTING
Kan Watanabe
∗
and Masaru Fukushi
†
Graduate School of Information Sciences, Tohoku University, Japan
Abstract
Volunteer computing (VC) is a type of Internet based parallel computing paradigm,
which allows any participants on the Internet to contribute their idle computing re-
sources. By exploiting the resources that can be found in millions of Internet comput-
ers, VC makes it possible to build a very large and high performance global computing
systems with a very low cost. However, VCs still have the problem of guaranteeing
computational correctness, due to the inherent unreliability of volunteer participants.
In this chapter, we fully study the sabotage-tolerance performance of several sabotage-
tolerance methods including popular voting method used in real VCs, and reveal their
drawbacks in terms of computation time and error rate. Then, based on the conclusion
from the comparison study, we propose a new job scheduling method for credibility-
based voting to efficiently attain the sabotage-tolerance of VCs, i.e. the mathematical
expectation of computational error rate is bounded by a given error rate specified as
reliability requirement. The key idea for efficient job scheduling is to choose jobs to
be executed prior to others considering the important feature that the necessary redun-
dancy for each job may change with time. Extensive simulation has shown that the
proposed job scheduling method reduces the overall computation time of VCs, while
guaranteeing the reliability requirement.
Key Words
: sabotage-tolerance, credibility-based mechanisms, reliability, job scheduling
1.
Introduction
1.1.
Volunteer Computing
Volunteer computing (VC) is a variation on the idea of metacomputing - using a network of
many separate computers as if they were one large parallel machine [1].
