Information Technology Reference
In-Depth Information
The performance difference between credibility-based 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 spot-checking and seem to
be non-saboteurs. On the other hand, in credibility-based voting, workers who survive a
number of spot-checking 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 credibility-based
voting shows better performance compared to
2
-FVSC.
550
0.002
M-first(M=2)
M-first(M=3)
M-first with spot-checking(M=2)
M-first with spot-checking(M=3)
Credibility-based voting(random)
Credibility-based voting(rr1)
ε
acc
M
-
f
i
r
s
t
(
M
=
2
)
M-first(M=3)
M-first with spot-checking(M=2)
M-first with spot-checking(M=3)
Credibility-based voting(random)
Credibility-based 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) Error-rate
(b) Computation time
T
Figure 12.
M
-first voting with spot-checking vs. Credibility-based 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, spot-checking-based methods can guarantee the reliability
condition
≤
acc
for any
s
. Note that the computation time of credibility-based 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 credibility-based voting; thus, the computation times of both credibility-based
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,
credibility-based 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).
