Information Technology Reference
In-Depth Information
While VC becomes easy to use, it still has a mandatory issue for reliable computing;
that is, saboteurs in VC systems may behave maliciously and return incorrect results, each
of which degrades computational correctness. Against these sabotaging, current VC frame-
works provide some sabotage-tolerance mechanisms such as credibility-based voting to
decrease error rate of a computation and improve the computational reliability of VC sys-
tems. However, those mechanisms are proposed and evaluated in unrealistic VC models
such as the simple random attack model without workers' defection. The performance and
drawbacks of those mechanisms are hidden in real VC systems. Therefore, current VC
frameworks such as BOINC provides the simplest sabotage-tolerance mechanism based on
a redundant computation, which significantly degrades the performance instead of ensuring
the reliability of computation.
This motivates us to reveal the sabotage-tolerance performance and drawbacks of cur-
rent sabotage-tolerance mechanisms, and improve them for higher performance and more
reliable VC systems. In this chapter, we discuss sabotage-tolerance mechanisms and job
scheduling methods used in those toward efficient sabotage-tolerance in real VC systems.
First, we evaluate the performance and effectiveness of current sabotage-tolerance mech-
anisms in more real VC model, e.g. collusion attack model. Then we put the efficiency
in perspective of job scheduling problems and propose an sabotage-tolerant job scheduling
method which works well in real VC systems.
3.
Sabotage-Tolerance Mechanisms and Performance
Evaluations
In this section, we will compare some basic mechanisms for sabotage tolerant VC systems.
We will first introduce sabotage-tolerance mechanisms such as voting and spot-checking
(Sec. 3.1), then compare the performance of those methods in terms of error rate and
computation time (Sec. 3.2). We will provide comprehensive comparison study of voting
methods, a checking method, and their hybrid methods to reveal their sabotage tolerance
performance and drawbacks. We will conclude this section with the brief summary obtained
by the comparison study.
3.1.
Sabotage-Tolerance Mechanisms
3.1.1.
Simple Voting
The basic approach to the sabotage-tolerance of VC systems is voting. Each job is replicated
and redundantly allocated to several workers so that a master can collect several results and
compare their values. The results collected for a job are then classified into groups (called
result groups) according to their values. The master decides which result group should
be accepted as the final result of the job through voting. Two major voting methods are
M
-majority and
M
-first voting [36].
• M
-Majority voting: This method collects
M
candidate results and accepts the result
group which collects the largest number of results as the final result.
