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
