Information Technology Reference
In-Depth Information
and
ENR
should be selected prior to others during job scheduling. If jobs are selected in
the ascending order of
EC
J
without considering the number of results, the jobs for which
erroneous results have been returned will be selected many times since the presence of in-
correct results makes it more difficult to increase the jobs' credibility . Such job scheduling
will cause performance degradation because of unnecessary job allocations, as verified in
our performance evaluation presented in Sec. 4.3.2.. Therefore, as described above, the
proposed job scheduling method selects jobs in the ascending order of
ENR
and
EC
J
.
4.2.3.
Scheduling Cost
Next, the scheduling cost is analyzed for both the round-robin and our proposed methods.
In VC systems, scheduling is the repetitive process of allocating jobs and receiving results.
As described in this chapter, the scheduling cost is defined as the time (worker's waiting
time) to select one job for a worker when the master receives a result from the worker.
Let
t
c
be the time required for the master to calculate a credibility of one job,
C
J
; also,
t
e
is the time to calculate the
ENR
of one job. The scheduling cost at time step
t
(
t
-th unit
time) is denoted as
Cost(t)
. The scheduling cost varies according to when it is calculated.
Therefore, we calculate
Cost(t)
and mean of
Cost(t)
for both methods.
In the round-robin method [23], when the master receives a result for a normal job
j
,
the master simply calculates only
C
J
(j)
in
t
c
to check whether it reaches the threshold or
not. If the master receives a result for a spotter job, the result will affect
C
J
of several jobs
because of backtracking or updating of the credibility. The number of jobs which need the
update of the credibility at time step
t
is, at most,
t
because the number of results produced
by
w
is, at most,
t
even if
w
can return a result in every time step. The scheduling cost for
the round-robin method, i.e.
Cost
orig
(t)
, is calculated as
Cost
orig
(t)=t
c
((1 − q)+qt).
(19)
Time step
t
changes from 1 to
T
, where
T
is the overall computation time of the com-
putation represented in unit times. The average of
Cost
orig
(t)
, i.e.
E(Cost
orig
)
is given
as
T
X
E(Cost
orig
)=
1
T
Cost
orig
(t)
t=1
= t
c
((1 − q)+
q(T +1)
2
).
(20)
Because the round-robin method is the simplest scheduling method, this cost is the mini-
mum required for credibility-based voting.
In the proposed method, when the master receives a result for a normal job
j
, the master
calculates
EC
J
(j)
and
ENR(j)
in addition to
C
J
(j)
.
EC
J
(j)
and
ENR(j)
must also be
updated when a normal job
j
is allocated to a worker (as shown in lines 13 - 16 in Fig.
??
).
Therefore, for each allocation of a normal job (probability
1 − q
), the master calculates
EC
J
(j)
and
ENR(j)
twice. If the master receives a result for a spotter job, the master
calculates
EC
J
and
ENR
in addition to
C
J
for, at most,
t
jobs as described above. The
