Information Technology Reference
In-Depth Information
Contrary to the case of
M
-majority voting, the computation times of
M
-first voting
depends on the value of
s
and
f
.At
s =0
or
f =0
, the computation times of
M
-first
voting are the same as those of
M
-majority voting because each job finishes with
M
results,
each of which has the correct value and matches each other. If there are incorrect results,
each job may have more than
M
results, which increases the computation time. The mean
number of collected results increases with the ratio of the number of incorrect results to all
results. Thus, as
s
and
f
increase, the computation times of
M
-first voting also increase.
0.5
500
M=1
M=2,Majority
M=3,Majority
M=2,M-first
M=
3
,M-
f
i
r
s
t
ε
acc
M=1
M=
2
,M
a
j
o
rity
M=3,Majorit
y
M=2,M-first
M=3,M-first
450
0.4
400
350
0.3
300
0.2
250
200
0.1
150
0
100
0
0.2
0.4
0.6
0.8
1
0
0.2
0.4
0.6
0.8
1
c
c
(a) Error-rate
(b) Computation time
T
Figure 7.
M
-first voting vs.
M
-majority voting for colluding rate
c
(
acc
=0.01
,
f =0.35
,
s =1
,
p
d
=0
, random scheduling).
Colluding rate
c
Fig.7(a) shows error rate of each voting method for colluding rate
c
.
This figure shows error rates of both
M
-majority and
M
-first voting methods increase with
c
. Since the number of matching incorrect results increases in proportion to
c
, those results
tend to be accepted as majority ones. When
c
is small, the values of incorrect results do
not match each other, resulting in small error rate in
M
-first voting. However, the error rate
of
M
-first voting dramatically increases as
c
increases. This result indicates that
M
-first
voting works well only when
c
is small.
Fig.7(a) also shows that error rates of
2
-first voting and
3
-majority voting are the same
at
c =1
.In
3
-majority voting, some one of result groups
G
X
has more than 2 results
because there are only two result groups, i.e. the group of correct results and the group of
incorrect (matching) results. Since the number of results in the other group is smaller than
2,
G
X
is accepted as the final result. Here,
2
-first voting also accepts
G
X
regardless of the
order of results production; thus, the error rates of
2
-first voting and
3
-majority voting are
the same. Generally, the error rates of
M
-first voting and
(2M − 1)
-majority voting are the
same at
c =1
, while the computation time of
M
-first voting is smaller since the number of
required results is from
M
to
(2M − 1)
.
Fig.7(b) shows computation time of each voting method for colluding rate
c
. The com-
putation time of
M
-majority voting stays constant for any
c
as the cases of
s
and
f
because
each job finishes with just
M
results. On the other hand, in cases of
M
-first voting, the
computation time changes with the value of
c
. This is because there are some jobs finished
