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