Information Technology Reference
In-Depth 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 credibility-based voting is one feasible approach for realizing high-performance
and reliable VC systems.
4.
Expected-Credibility-Based Job Scheduling Method
As shown in the comparison study of the previous section, credibility-based voting is the
most promising approach for high-performance 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 credibility-based 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 credibility-based
voting is one feasible approach for realizing high-performance and reliable VC systems.
In this section, we propose a dynamic job scheduling method for credibility-based vot-
ing, which is referred as “expected-credibility-based job scheduling” in this chapter. We
will first discuss the job scheduling problem in credibility-based voting (Sec. 4.1), then pro-
pose expected-credibility-based 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 sabotage-tolerance 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 non-redundant computation. Similarly, spot-checking with the
spot-check 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 credibility-based 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 spot-checking. In
this case, the order of execution of jobs directly affects the total number of results.Therefore,
in credibility-based 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 sabotage-tolerant VC systems using credibility-based 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
.
