Information Technology Reference
InDepth Information

The actual values of computation times in real VCs become larger than those in
the basic model (i.e.
p
d
=0
).
Thus, as shown clearly in the comparison study, devising an efficient job scheduling
method for credibilitybased voting is one feasible approach for realizing highperformance
and reliable VC systems.
4.
ExpectedCredibilityBased Job Scheduling Method
As shown in the comparison study of the previous section, credibilitybased voting is the
most promising approach for highperformance and reliable VC systems since it guarantees
the reliability condition for any situation and tends to show better performance than
M

FVSC. Also, the computation time of credibilitybased voting largely depends on the job
scheduling method. The original scheduling method used in [23], i.e. round robin method,
is not efficient. Therefore, devising an efficient scheduling method for credibilitybased
voting is one feasible approach for realizing highperformance and reliable VC systems.
In this section, we propose a dynamic job scheduling method for credibilitybased vot
ing, which is referred as “expectedcredibilitybased job scheduling” in this chapter. We
will first discuss the job scheduling problem in credibilitybased voting (Sec. 4.1), then pro
pose expectedcredibilitybased job scheduling method (Sec. 4.2). Then, we will provide
comparison study of proposed and other job scheduling methods to reveal their performance
(Sec. 4.3).
4.1.
Job Scheduling Problems and Motivations
A sabotagetolerance mechanism generally requires some extra computation time (over
head) because of a redundant computation. For example, when each job is replicated and
allocated to
M
workers for a voting, it increases the overall computation time by
M
times
compared to the case of nonredundant computation. Similarly, spotchecking with the
spotcheck rate
q
[23] increases the computation time by
1/(1 − q)
times.
In basic voting methods, the necessary number of results for each job is fixed in advance
(e.g.
M
matching results are required in
M
first voting). In this case, the order of execution
of jobs does not affect the total number of results produced for a computation. Even if the
order of execution of jobs is changed, the overall computation time remains unchanged.
In contrast, with credibilitybased voting, the necessary number of results for each job
is not fixed in advance because it depends on the credibility of each result. The credibility
of result changes as the computation proceeds, depending on the result of spotchecking. In
this case, the order of execution of jobs directly affects the total number of results.Therefore,
in credibilitybased voting, job scheduling method have a considerable impact on the over
head and the computation time of the computation as shown in the previous section.
In the sabotagetolerant VC systems using credibilitybased voting, the job scheduling
problem is summarized as follows:
select a job that should be allocated to an idle worker prior to other jobs for re
ducing computation time
T
to the greatest extent possible, while guaranteeing
the computational correctness as
≤
acc
for any given
acc
.