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
 
Search WWH ::




Custom Search