Information Technology Reference
In-Depth Information
seems to efficient to enhance the reliability of computation. Spot-checking can be simply
combined with the simple voting methods. We focus on the hybrid method of
M
-first voting
and spot-checking, i.e.
M
-first voting with spot-checking, and credibility-based voting. The
relation among those sabotage-tolerance methods are summarized as following.
•
simple voting methods
The master allocates a job to several workers for majority decision.
-
M
-majority voting
-
M
-first voting
•
spot-checking-based methods
The master allocates spotter jobs with probability
q
in addition to allocate normal
jobs.
-
M
-first voting with spot-checking (
M
-FVSC in short)
-
Credibility-based voting
0.02
550
M-first(M=2)
M-first(M=3)
M-first with spot-checking(M=2)
M-first with spot-checking(M=3)
Credibility-based voting(random)
Credibility-based voting(rr1)
ε
acc
M
-
f
i
r
s
t
(
M
=
2
)
M-first(M=3)
M-first with spot-checking(M=2)
M-first with spot-checking(M=3)
Credibility-based voting(random)
Credibility-based voting(rr1)
500
0.015
450
400
0.01
350
300
0.005
250
200
0
150
0
0.2
0.4
0.6
0.8
1
0
0.2
0.4
0.6
0.8
1
s
s
(a) Error-rate
(b) Computation time
T
Figure 10.
M
-first voting with spot-checking vs. Credibility-based voting for sabotage rate
s
(
acc
=0.01
,
f =0.35
,
c =0.0
,
q =0.1
,
p
d
=0
, random scheduling with blacklisting).
Sabotage rate
s
in cases with blacklisting
Fig.10 (a) shows error rate of each method for
sabotage rate
s
when no saboteurs collude (
c =0
). This figure shows that each sabotage-
tolerance method guarantees the reliability condition
≤
acc
=0.01
when
c =0
. The
error rates of
M
-first voting and
M
-FVSC are 0. This is true because every incorrect result
has a different value and no incorrect result will be accepted as majority. On the other hand,
in credibility-based voting, some incorrect results can be accepted as final ones, which
increases the error rate of the computation. This is because credibility-based voting reduces
the number of redundant results as much as possible (as long as the error rate does not
exceed
acc
) for higher performance of VC systems.
