Information Technology Reference
In-Depth Information
Figure 3. Sabotage model of VC systems .
2.3.2.
Sabotage Model
Recently, the need of the sabotage-tolerance is pointed out in [24, 25, 26, 27, 32] because
VC allows anyone on the Internet to join a computation. Different from grid computing
system which shares managed reliable computers within or among organizations, workers
of VC system are owned and managed by general users. The workers may behave erratically
due to hardware/software failures or virus infection, or may behave maliciously to falsify
the results of jobs, each of which results in sabotage to the computation. It is reported
in [27] that a large fraction of workers (about 35 percent) actually returned at least one
incorrect results in a real VC.
In addition, the presence of malicious workers (saboteurs) is a serious issue for VC sys-
tems to guarantee the computational correctness. Malicious workers can sabotage job ex-
ecution intentionally by returning erroneous results. Traditional fault-tolerance techniques
such as using parity and checksum schemes will not be effective, because they cannot pro-
tect against intentional attacks by saboteurs who can disassemble the code. Thus, sabotage-
tolerance is a mandatory issue for VC systems in order to make them reliable and viable.
To discuss the sabotage-tolerance problem of VC systems, Sarmenta [23] proposed the
following sabotage model of VCs. Figure 3 illustrates the sabotage model.
•
A certain faulty fraction
f
of the
W
workers are assumed to be saboteurs who might
return erroneous (incorrect) results.
•
Each saboteur is assumed to return an erroneous result with a constant probability
s
,
which is known as the sabotage rate.
•
The values of
f
and
s
are unknown to the master.
In VCs with saboteurs, jobs that finish with erroneous results are called erroneous jobs.
At the end of the computation, an error rate
can be calculated as the ratio of erroneous jobs
to all jobs. The purpose of sabotage-tolerance in VCs is decreasing error rate as needed
for the computation.
Using no sabotage-tolerance mechanisms, the error rate increases in proportion to the
number of saboteurs. Let
T
be the time taken to finish all jobs of a computation, i.e. the
