Information Technology Reference
In-Depth Information
with
M
incorrect results when saboteurs collude. Since larger
c
increases the number of
such jobs, it decreases the computation time, while increasing error rate.
0.05
3000
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
0.045
2500
0.04
0.035
2000
0.03
0.025
1500
0.02
1000
0.015
0.01
500
0.005
0
0
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8
pd
pd
(a) Error-rate
(b) Computation time
T
Figure 8.
M
-first voting vs.
M
-majority voting for defection rate
p
d
(
acc
=0.01
,
s =0.1
,
c =1
,
P
up
(steady)=0.8
, random scheduling).
Defection rate
p
d
Fig.8 shows error rate and computation time of each voting method
for defection rate
p
d
under the condition of
P
up
(steady)=0.8
. The value of
p
u
is set
corresponding to
p
d
so that 80% of workers are participating in the system, on average. For
instance, when
p
d
=0.1
,
p
u
is set to
0.4
. This figure shows error rates of voting methods
stay constant, while computation times increase with
p
d
.
In the random defection model shown in Sec. 2.3.3, the expectation of the computation
time for
M
-majority voting is given as following. By supposing each worker has the same
property, the mean number of active state workers
W
up
at each time step is given by eq.(15).
Note that
P
up
(steady)
is constant.
W
up
= W × P
up
(steady)
= W ×
p
d
p
u
+ p
d
.
(15)
When a worker
W
n
gets a job which takes
i
unit times to process,
W
n
returns a result
for the job with probability
P(i)=(1− utod
n
)
i
. If all workers function at the same speed
and return results within 1 unit time,
W
up
workers get jobs in each unit time and return their
results with probability
P(1)
on average. Since
M
results are collected for all
N
jobs, the
expectation of the computation
T
majority
(M)
is given by following.
N
W
up
× P(1)
T
majority
(M)=M ×
N
W × P
up
(steady)
×
1
1 − p
d
.
= M ×
(16)
Eq.(16) shows the computation time is proportional to
1/(1 − p
d
)
. The computation
time of
M
-first voting also increases with
p
d
as shown in Fig.8(b). Thus, the actual values
