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
