Information Technology Reference
In-Depth Information
550
0.02
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-first(M=2)
M-first ( M = 3 )
M-first with spot-c heck i n g ( M=2)
M-first wit h s p o t-checking(M=3)
Credibil i t y -based voting(random)
C r e d ibility-based voting(rr1)
500
0.015
450
400
0.01
350
300
0.005
250
0
200
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 13. 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 without
blacklisting).
Fig.13 (a) also shows that error rates of M -FVSC increase in proportion to s and exceed
acc when s ≥ 0.25 and M =2 . This result indicates that only using spot-checking is in-
adequate to guarantee the reliability condition acc . It requires redundant computation
with larger redundancy ( M ≥ 3 in this case) to satisfy the reliability condition for any s .
Although spot-checking detects saboteurs and eliminates incorrect results, in cases without
blacklisting, those saboteurs rejoin to the system and produce incorrect results with proba-
bility s , which remain in the system until the end of the computation. Since the number of
remaining incorrect results is proportional to s , the error rate increases with s and reaches
its peak at s =1 . Thus, to guarantee the reliability condition for any s , the redundancy M
should be set to a larger value ( M =3 ) supposing the worst case s =1 .
Fig.13 (b) shows the computation time of each method. Different from the cases with
blacklisting (Fig.11), the computation times of spot-checking-based methods increase with
s . This is true because results from saboteurs remain in the system as candidate results of
voting, even if s is large. For larger s , saboteurs are easily detected and eliminated from
the system; however they return to the system and produce their results in cases without
blacklisting. The number of remained incorrect results which do not match with correct
ones increases with s , while decreasing the number of correct results produced in each unit
time. Thus, in cases without blacklisting, larger s decreases the number of correct results
which finish jobs, and increases the computation time.
Fig.13 (b) also shows that the computation time of credibility-based voting is almost
the same as that of 2 -FVSC at acc =0.01 . In this case, almost all jobs require two results
in credibility-based voting like as the case of Fig.12. For acc =0.01 , M -FVSC requires
the redundancy at least M =3 to satisfy the reliability condition for any s . Also, this figure
shows that credibility-based voting outperforms 3 -FVSC. The differences of computation
times between those methods range from 110 ( T = 340 and T = 230 at s =0 ) to 190
( T = 520 and T = 330 at s =1 ).
Fig.14 shows the error rate and computation time of each method at acc =0.001 . This
Search WWH ::

Custom Search