Information Technology Reference
of computation times in real VCs become larger than those in the basic model (i.e. p d =0 ),
since workers in real VCs frequently defect and rejoin the system corresponding with non-
zero p d . For example, when p d =0.5 , it doubles the computation times compared with
those in the basic model.
M-first(c=0. 1 )
(b) Computation time T
Figure 9. M -first voting vs. M -majority voting for redundancy M ( acc =0.01 , f =0.35 ,
s =1 , p d =0 , random scheduling).
Redundancy M Fig.9 shows error rate and computation time of each voting method for
redundancy M . This figure shows error rates of both M -majority and M -first voting meth-
ods decrease with M , while increasing the computation times.
This figure shows that M -first voting decreases error rate efficiently when c is small
(e.g. c =0.1 ). For example, two correct results (i.e. 2 -first voting) is enough to satisfy
the condition ≤ acc =0.01 in this case. On the other hand, M -majority voting does not
decrease error rate as M -first voting and requires huge redundancy ( M =7 in this case) to
satisfy the condition ≤ acc . This means that the computation time of M -majority voting
is huge (e.g. T = 700 at M =7 ), and that of M -first voting is small (e.g. T = 300 at
M =2 ) for the same condition acc =0.01 .
This figure also shows that, when c is large, both M -majority and M -first voting meth-
ods do not decrease error rate efficiently and require huge redundancy to satisfy the reliabil-
ity condition ≤ acc . Even if M =10 , error rates of both methods are around 0.1 or larger
when c =1 . The required values of M obtained from eq.(7) for M -first voting are M =15
for acc =0.05 , M =29 for acc =0.01 and over 50 for acc =0.001 , respectively. This
result indicates that both M -majority and M -first voting methods work well only when c
is small. Thus, there are needs to introduce such a novel sabotage-tolerance method that
efficiently decreases error rates even if saboteurs frequently collude.
3.2.3. M -First Voting with Spot-Checking vs. Credibility-Based Voting
Here, we evaluate the performance of spot-checking based methods. As spot-checking
can remove saboteurs from the systems by directly checking their behavior, this technique