Information Technology Reference

In-Depth Information

of computation times in real VCs become larger than those in the basic model (i.e.
p
d
=0
),

since workers in real VCs frequently defect and rejoin the system corresponding with non-

zero
p
d
. For example, when
p
d
=0.5
, it doubles the computation times compared with

those in the basic model.

0.5

1600

Majority(c=0.1)

Majority(c=1.0)

M-first(c=0.
1
)

M-first(c=1.0)

Majority(c=0.1)

Majority(c=1.0)

M-first(c=0.1)

M-first(c=1.0)

ε
acc

1400

0.4

1200

1000

0.3

800

0.2

600

400

0.1

200

0

0

1

2

3

4

5

6

7

8

9 10

1

2

3

4

5

6

7

8

9 10

M

M

(b) Computation time
T

(a) Error-rate

Figure 9.
M
-first voting vs.
M
-majority voting for redundancy
M
(
acc
=0.01
,
f =0.35
,

s =1
,
p
d
=0
, random scheduling).

Redundancy
M
Fig.9 shows error rate and computation time of each voting method for

redundancy
M
. This figure shows error rates of both
M
-majority and
M
-first voting meth-

ods decrease with
M
, while increasing the computation times.

This figure shows that
M
-first voting decreases error rate efficiently when
c
is small

(e.g.
c =0.1
). For example, two correct results (i.e.
2
-first voting) is enough to satisfy

the condition
≤
acc
=0.01
in this case. On the other hand,
M
-majority voting does not

decrease error rate as
M
-first voting and requires huge redundancy (
M =7
in this case) to

satisfy the condition
≤
acc
. This means that the computation time of
M
-majority voting

is huge (e.g.
T = 700
at
M =7
), and that of
M
-first voting is small (e.g.
T = 300
at

M =2
) for the same condition
acc
=0.01
.

This figure also shows that, when
c
is large, both
M
-majority and
M
-first voting meth-

ods do not decrease error rate efficiently and require huge redundancy to satisfy the reliabil-

ity condition
≤
acc
. Even if
M =10
, error rates of both methods are around 0.1 or larger

when
c =1
. The required values of
M
obtained from eq.(7) for
M
-first voting are
M =15

for
acc
=0.05
,
M =29
for
acc
=0.01
and over
50
for
acc
=0.001
, respectively. This

result indicates that both
M
-majority and
M
-first voting methods work well only when
c

is small. Thus, there are needs to introduce such a novel sabotage-tolerance method that

efficiently decreases error rates even if saboteurs frequently collude.

3.2.3.
M
-First Voting with Spot-Checking vs. Credibility-Based Voting

Here, we evaluate the performance of spot-checking based methods. As spot-checking

can remove saboteurs from the systems by directly checking their behavior, this technique