Information Technology Reference
In-Depth Information
bility condition
≤
acc
for any
f
. In contrast to the case of sabotage rate
s
(Fig.12), error
rates of spot-checking-based methods increase with
f
, i.e. the number of saboteurs. This
is true because, as
f
becomes larger, more saboteurs survive spot-checking and produce
incorrect results, which remain in the system until the end of the computation. Since the
number of remaining incorrect results is proportional to
f
, the error rate increases with
f
and reaches its peak at
f = f
max
. Thus, to guarantee the reliability condition for any
f
, the
redundancy
M
should be set to a larger value supposing the worst case
f = f
max
.
Fig.15 (b) shows the computation time of each method. The computation time of
M
-
first voting stays almost constant for any
f
, while those of spot-checking-based methods
increase with
f
because the results produced by detected saboteurs are invalidated. As
f
increases, more saboteurs are detected and eliminated from the system, resulting in decre-
ment of the number of valid results. This result indicates that the value of
f
has a significant
impact on the computation time of spot-checking-based methods.
400
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(
r
r1)
ε
acc
M-first(M=2)
M-first(M=3)
M-first with s
p
ot-checking(M=2)
M-f
i
rst
w
ith spot-checking(M=3)
Credibility-based voting(random)
Credibility-based voting(rr1)
380
360
0.0015
340
320
0.001
300
280
260
0.0005
240
220
0
200
0 0.05 0.1 0.15 0.2 0.25 0.3 0.35
0
0.05 0.1 0.15 0.2 0.25 0.3 0.35
f
f
(a) Error-rate
(b) Computation time
T
Figure 16.
M
-first voting with spot-checking vs. Credibility-based voting for fraction
f
(
acc
=0.001
,
s =0.1
,
c =1.0
,
q =0.1
,
p
d
=0
, random scheduling without blacklisting).
Fig.16 shows the error rate and the computation time of each method in cases without
blacklisting. This figure shows that error rates of both
2
-first voting and
2
-FVSC exceed
acc
for
f ≥ 0.2
. Since the value of
f
is unknown beforehand, redundancy (i.e.
M
) should be
set to
3
supposing the worst case
f = f
max
. Note that larger
M
increases the computation
time, while decreasing error rate. From Fig.16 (b), it is clear that the computation times
of
3
-first voting and
3
-FVSC are larger than that of credibility-based voting. For example,
the computation time of
3
-first voting is around 310, while that of credibility-based voting
using round robin scheduling is around 280. This result indicates that
M
-FVSC requires
huge redundancy
M
to guarantee the reliability condition for any
s
and
f
since it must
suppose the worst case (
s =1
and
f = f
max
).
Fig.16 (b) also shows that, when
f
is very small, credibility-based voting may be
slow. For example, when
f =0
, the computation time of
2
-FVSC is smaller than that
of credibility-based voting, while the error rates of both methods are 0 at
f =0
. This result
indicates that credibility-based voting may perform excess redundant computation when
f