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