Information Technology Reference
InDepth Information
The performance difference between credibilitybased voting and
M
FVSC comes
from the difference of the required number of results to finish a job. In
M
FVSC, all jobs
require at least
M
results, even if workers survive a number of spotchecking and seem to
be nonsaboteurs. On the other hand, in credibilitybased voting, workers who survive a
number of spotchecking have large credibility and produce large credibility results. If the
credibility of a result is large enough (larger than threshold
θ =1−
acc
), a job having the
result can be finished with only that result, i.e. the redundancy is 1. Thus, the mean number
of the required results to finish jobs can be smaller than two. This is why credibilitybased
voting shows better performance compared to
2
FVSC.
550
0.002
Mfirst(M=2)
Mfirst(M=3)
Mfirst with spotchecking(M=2)
Mfirst with spotchecking(M=3)
Credibilitybased voting(random)
Credibilitybased voting(rr1)
ε
acc
M

f
i
r
s
t
(
M
=
2
)
Mfirst(M=3)
Mfirst with spotchecking(M=2)
Mfirst with spotchecking(M=3)
Credibilitybased voting(random)
Credibilitybased voting(rr1)
500
0.0015
450
400
0.001
350
300
0.0005
250
0
200
0
0.2
0.4
0.6
0.8
1
0
0.2
0.4
0.6
0.8
1
s
s
(a) Errorrate
(b) Computation time
T
Figure 12.
M
first voting with spotchecking vs. Credibilitybased voting for sabotage rate
s
(
acc
=0.001
,
f =0.35
,
c =1.0
,
q =0.1
,
p
d
=0
, random scheduling with blacklisting).
Fig.12 shows error rate and computation time of each method at
acc
=0.001
. Even if
acc
changes from 0.01 to 0.001, spotcheckingbased methods can guarantee the reliability
condition
≤
acc
for any
s
. Note that the computation time of credibilitybased voting
depends on
acc
. As shown in Fig.11 (b) and Fig.12 (b), the computation time of credibility
based voting becomes larger for smaller
acc
. For smaller
acc
, the number of jobs finished
with only one result becomes smaller, since workers who have enough high credibility
(larger than
1 −
acc
) become smaller. When
acc
=0.001
, almost all jobs require two
results in credibilitybased voting; thus, the computation times of both credibilitybased
voting and
2
FVSC become almost the same.
Sabotage rate
s
in cases without blacklisting
Fig.13 (a) shows the error rate of each
method for sabotage rate
s
. This figure shows that, even in cases without blacklisting,
credibilitybased voting guarantees the reliability condition
≤
acc
=0.01
. This is true
because the calculation formula of credibility changes in accordance with the availability of
blacklisting. If blacklisting is not available, a saboteur can rejoin to the system and produce
incorrect results permanently. Thus, the credibility given to each worker, i.e. the probability
of returning correct results, becomes smaller than that in cases with blacklisting as shown
in eqs.(8)  (9).