Information Technology Reference
In-Depth Information
• M
-first voting: This method collects at least
M
candidate results and accepts the
result group which first collects
M
matching (the same) results as the final result.
The benefit of these voting methods is its simple principle, which eases its implemen-
tation. The
M
-first voting is supported by the main VC middle-ware BOINC [17, 20] and
is widely used by major VC projects [11, 12, 15]. On the contrary, a major weakness lies in
inefficient use of huge number of available workers, since the degree of redundancy is static
and must be specified by a project owner before starting the computation. The
M
-majority
voting always generates a fixed number of candidate results for each job and the
M
-first
voting always collects a fixed number of matching results, no matter how reliable each re-
sult is. The reliability of each worker may differ from one another and change dynamically
with time; hence, any statically chosen redundancy value will result in waste of a number
of useful workers for unnecessary redundant computations.
If all workers function at the same speed and execute a job in a unit time, the theoretical
expectation of error rate of
M
-first voting is given by eq.(7) [1].
2M−1
X
2M−1
C
j
φ
j
(1 − φ)
2M−1−j
,
voting
(M, φ)=
(7)
j=M
where
φ
represents the ratio of incorrect results to all produced results.
φ
is equal to
f × s
when
c
, i.e. colluding rate, is equal to
1
.
3.1.2.
Spot-Checking
Spot-checking [23] is devised to check whether a worker is a saboteur or not directly and
is used in web-based VC framework “Bayanihan” [22, 21]. In this technique, a master
sometimes assigns a spotter job whose correct result is already known to the master. If
a worker returns a result which does not match the correct one, the master can catch the
worker as a saboteur.
When the master catches a saboteur by spot-checking, the following two methods can
be used:
•
Backtracking: The master backtracks (invalidates) all results returned by the saboteur
because each might be an incorrect one.
•
Blacklisting: The master puts saboteur's identification information (e.g. IP address)
on a blacklist to prevent the saboteur from returning results or getting any more jobs.
Backtracking and blacklisting can be used simultaneously for efficient sabotage-
tolerance. However, blacklisting is not always effective for VC systems. Although sabo-
teurs can be blacklisted based on their IP addresses, it is not difficult for a saboteur to rejoin
the computation as a new worker. Requiring more reliable identification information such
as home address will make the blacklisting more effective. However, it also diminishes
volunteers' incentive to join the VC system. Based on this trade-off, we must consider both
VC systems with and without blacklisting to meet the variant condition of real VCs.
Spot-checking is an effective technique in that master can detect saboteurs with a high
degree of confidence unless returned results match the correct one by accident. However,
