Information Technology Reference
In-Depth Information
spot-checking (and similar techniques such as quizzes [26] and sampling [28]) also has
some difficulties which must be considered in practical use; master must generate spotter
jobs which are not easily identifiable as spotter ones. For this problem, one possible way
is implied in [1] that spotter job can be generated by executing a normal job at a reliable
node (e.g. master) before starting a computation project. In addition, even if backtracking
and blacklisting are used with the spot-checking, using only this technique for sabotage-
tolerance purpose will need a huge number of spotter jobs to obtain highly reliable results.
An experiment of VC [27] concluded that this technique will require longer computation
time than the simple voting like
M
-first voting for achieving lower error rate than
2 ×
10
−4
because spot-checking will not efficiently detect saboteurs who return incorrect results
infrequently (i.e. saboteurs of small
s
).
3.1.3.
Credibility-Based Voting
Combining the idea of voting and spot-checking to cover their disadvantages, Sarmenta
[23] proposes a new voting method, referred to as “credibility-based voting” in this chapter.
In this method, each system element such as a worker, result, result group, and job is as-
signed a credibility value that represents its correctness. Spot-checking is used to estimate
worker's credibility. Every worker and result has different credibility, which collectively
affect the credibility of the result groups. A job is finished when the credibility of any result
group reaches a threshold
θ
. Therefore, different from
M
-first voting, the necessary num-
ber of results to finish a job is not fixed but rather flexible in accordance with the worker's
behaviour. This mechanism reduces unnecessary redundant computations.
Furthermore, this method can guarantee that the mathematical expectation of the er-
ror rate is below an arbitrary acceptable error rate
acc
for any parameters (i.e. reliability
condition
≤
acc
is satisfied for any
s
and
f
) by setting two conditions: (1) threshold
θ =1−
acc
, and (2) unknown parameter
f
satisfies
f ≤ f
max
, where
f
max
is the upper
limit of
f
and is a known value. This condition implies that the number of saboteurs in
W
workers is, at most,
f
max
× W
.
The details of credibility-based voting is described here with the definitions of the cred-
ibility [23]. The credibility of a worker
w
(denoted by
C
W
(w)
) is determined by how many
times
w
survives spot-checking (how many times
w
returns the correct result for spotter
jobs). When blacklisting is used, if worker
w
wb
survives spot-checking
k
times,
C
W
(w
wb
)
is given by eq. (8).
(
1 − f
max
,
if
k =0
C
W
(w
wb
)=
(8)
f
max
1 −
(1−f
max
)×ke
,
otherwise.
Therein,
e
is Napier's constant. When blacklisting is not used, the credibility of worker
w
wob
,
C
W
(w
wob
)
, is given by eq.(9).
(
1 − f
max
,
if
k =0
C
W
(w
wob
)=
(9)
1 −
f
max
,
otherwise.
k
The credibility of a result
r
produced by worker
w
(denoted by
C
R
(r)
) is equal to
C
W
(w)
.
C
R
(r)=C
W
(w).
(10)
