Information Technology Reference
In-Depth Information
is very small. This is true because credibility-based voting calculates credibility and de-
termine the redundancy supposing that the values of unknown parameters
s
and
f
are the
worst values (
f = f
max
etc.) to guarantee the reliability condition for any combination of
s
and
f
. Therefore, in some cases where error rate is small, credibility-based voting may
perform redundant computation excessively and degrade the performance of VC systems,
as
M
-first voting with larger
M
does.
One of the solution to ease this performance degradation is focusing on job scheduling
methods of credibility-based voting. Since credibility-based voting with any scheduling
method guarantees the reliability condition, there is no drawback to use faster job schedul-
ing method (round robin method in this case). As shown in Fig.16 (b) and others, there is
a clear difference between the computation time of round robin method and that of random
method. Thus, we present a novel job scheduling method which enhances the performance
of credibility-based voting in the next section.
0.002
550
M-first(M=2)
M-first(M=3)
M-first with spot-checkin
g
(M=2)
M-first with spot-checking(M=3)
Credibility-based voting
(
random)
Credibility-based voting(rr1)
ε
acc
M-first(M=2)
M
-
f
i
r
s
t
(
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
c
c
(a) Error-rate
(b) Computation time
T
Figure 17.
M
-first voting with spot-checking vs. Credibility-based voting for colluding rate
c
(
acc
=0.001
,
s =0.1
,
f =0.35
,
q =0.1
,
p
d
=0
, random scheduling with blacklisting).
Colluding rate
c
Fig.17 shows error rate and computation time of each method for col-
luding rate
c
in cases with blacklisting. Error rates of all methods increase with
c
, because
larger
c
increases the number of matching incorrect results and the probability of their being
final result. The value of
c
is also unknown to the master beforehand like
s
and
f
. Thus,
to guarantee the reliability condition for any
c
, the redundancy
M
should be set to a larger
value by supposing the worst case
c =1
. Note that credibility-based voting guarantees the
reliability condition for any
c
. The computation times of spot-checking-based methods stay
constant for any
c
because almost all saboteurs are eliminated from the system regardless
the value of
c
.
Fig.18 shows error rate and computation time of each method in cases without black-
listing. This figure shows that the error rates of both
2
-first voting and
2
-FVSC exceed
acc
when
c ≥ 0.65
. The redundancy
M
should be set to larger than 3; however, such large
