Information Technology Reference
In-Depth Information
Fig.10 (b) shows computation time of each method. Compared to
M
-first voting,
M
-
FVSC takes longer computation time for the same
M
. Due to spot-checking, the computa-
tion time increases by following two reasons. (1) Spotter jobs allocated to workers are extra
ones, which wastes worker resources. It increases total amount of jobs and computation
time by
1/(1 − q)
times. (2) Saboteurs detected by spot-checking and results produced by
those saboteurs are eliminated from the system. This reduces the number of workers and
the number of results produced in each unit time.
Fig.10 (b) also shows that, in cases with blacklisting, computation times of spot-
checking-based methods (credibility-based voting and
M
-FVSC) stay constant for larger
s
. Since spot-checking detects a saboteur with probability
s
, all saboteurs can be detected
and eliminated from the system when
s
is larger than a certain value. All results produced
by the saboteurs are invalidated regardless of the value of
s
. Therefore, sabotage-rate
s
does
not affect on the computation time so much, when blacklisting is used.
0.02
550
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
450
0.015
400
0.01
350
300
0.005
250
200
0
150
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 11.
M
-first voting with spot-checking vs. Credibility-based voting for sabotage rate
s
(
acc
=0.01
,
f =0.35
,
c =1.0
,
q =0.1
,
p
d
=0
, random scheduling with blacklisting).
Fig.11 (a) shows error rates of each method for sabotage rate
s
when saboteurs collude
(
c =1
). Different from the case of
c =0
(Fig.10 (a)), the error rate of
M
-first voting
becomes quit large. On the other hand, the error rates of spot-checking-based methods
are smaller since spot-checking eliminates incorrect results from saboteurs. This result
indicates that spot-checking is a promising approach to the reduction of error rates against
the collusion attack method.
Fig.10 (a) and Fig.11 (a) show that the error rates of spot-checking-based methods are
smaller than
acc
for any
s
, whether saboteurs collude (
c =1
) or not (
c =0
). Although
the values of
s
and
c
are unknown to the master, those method can guarantee the reliability
condition
≤
acc
=0.01
in this case.
From Fig.10 (b) and Fig.11 (b), it seems that credibility-based voting outperforms
M
-
FVSC. For satisfying the condition
≤
acc
=0.01
in cases with blacklisting, there is a
large difference of the computation time among those methods. For example, the computa-
tion time of credibility-based voting with round-robin scheduling is around 240 at
s =1
,
while that of
2
-FVSC is around 350.
