Information Technology Reference
In-Depth Information
500
0.02
M=1
M=2,Majority
M=3,Majority
M=2,M-first
M=3,M-first
ε
acc
M=1
M=2,Majority
M=3,Majority
M=2,M-first
M=3,M-first
450
0.015
400
350
0.01
300
250
0.005
200
150
0
100
0 0.05 0.1 0.15 0.2 0.25 0.3 0.35
0
0.05 0.1 0.15 0.2 0.25 0.3 0.35
f
f
(a) Error-rate
(b) Computation time
T
Figure 6.
M
-first voting vs.
M
-majority voting for fraction
f
(
acc
=0.01
,
s =1
,
c =0.1
,
p
d
=0
, random scheduling).
redundancy
M
decreases the error rate. When
M =1
, the error rate corresponds to the
ratio of the number of incorrect results because all incorrect results are accepted. Thus, the
error rate is equal to
f × s × N/N = fs
.
In the case of
M
-majority voting, the error rate for
M =2
is equal to that for
M =1
.
This means 2-majority voting does not perform meaningful redundant computation. In 2-
majority voting, both of two candidate results are incorrect with probability
(fs)
2
. Also,
one candidate result is incorrect and the other is correct with probability
2
C
1
×(fs)×(1−
fs)
. Since 2-majority voting randomly selects the final result from those candidates in this
situation, the incorrect one will be accepted with a probability of 50%. Thus, the error rate
of 2-majority voting is equal to
(fs)
2
+
2
C
1
×(fs)×(1−fs)×0.5=fs
.As
M
becomes
larger than three, majority voting performs well based on the principle of majority rule. For
example, at
s =0.2
and
f =0.35
in Fig.5(a), the error rate of 3-majority voting is around
0.01, while
fs=0.07
.
In the case of
M
-first voting, the error rate for
M =2
is very small compare to that for
M =1
. This means
M
-first voting performs good redundant computation and decreases
error rate even if the redundancy is the smallest (
M =2
). Also, for the same redundancy
(
M =3
), the error rate of
M
-first voting is less than that of
M
-majority voting for all
s
.
In
M
-first voting, incorrect results having the different values are difficult to be accepted
as the final result because
M
-first voting collects
M
matching results even if it already
holds
M
candidate results. This is why the error rate of
M
-first voting is less than that of
M
-majority voting for the same
M
.
Fig.5(b) and Fig.6(b) show computation time of each voting method for sabotage rate
s
and fraction
f
, respectively. The computation time of
M
-majority voting stays constant
for all
s
and
f
because each job finishes with just two results whether the results are correct
or not. Thus, the computation times are around
M × N/W = 200
for
M =2
and 300 for
M =3
, respectively. (There are minor differences between the simulation results and those
values since some jobs may have more than two results depending on the sequences of job
allocations and completion determinations.)
