Information Technology Reference
InDepth Information
is very small. This is true because credibilitybased 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, credibilitybased 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 credibilitybased voting. Since credibilitybased 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 credibilitybased voting in the next section.
0.002
550
Mfirst(M=2)
Mfirst(M=3)
Mfirst with spotcheckin
g
(M=2)
Mfirst with spotchecking(M=3)
Credibilitybased voting
(
random)
Credibilitybased voting(rr1)
ε
acc
Mfirst(M=2)
M

f
i
r
s
t
(
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
c
c
(a) Errorrate
(b) Computation time
T
Figure 17.
M
first voting with spotchecking vs. Credibilitybased 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 credibilitybased voting guarantees the
reliability condition for any
c
. The computation times of spotcheckingbased 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