Information Technology Reference
In-Depth Information
•
The expected number of results (
ENR
)
ENR(j)
is defined as
g
X
ENR(j)=
|G
i
| + d,
(17)
i=1
where
|G
i
|
represents the number of results in
G
i
.
The metric
ENR(j)
represents the number of results of job
j
when all
d
workers
return their results for job
j
.
•
Expected credibility (
EC
J
)
EC
J
(j)
is defined as
1≤a≤g
C
0
EC
J
(j)= max
G
(G
a
),
(18)
where
Q
P
T
(G
a
)
i6=a
P
F
(G
i
)
C
0
G
(G
a
)=
i6=n
P
F
(G
i
)
,
Q
P
Q
g
g
i=1
P
F
(G
i
)+
n=1
P
T
(G
n
)
(
P
T
(G
a
),
if
a 6= x
P
0
T
(G
a
)=
Q
i=1
C
W
(w
i
),
P
T
(G
a
) ×
if
a = x,
(
P
F
(G
a
),
if
a 6= x
P
0
F
(G
a
)=
Q
i=1
(1 − C
W
(w
i
)),
P
F
(G
a
) ×
if
a = x.
In those equations,
P
0
T
(G
a
)
(
P
0
F
(G
a
)
) is the probability that all results in
G
a
and all
d
workers are correct (incorrect).
The metric
EC
J
(j)
predicts the credibility of job
j
supposing that all
d
workers
return the same result, which joins the result group
G
x
, where
G
x
is the result group
which has a maximum credibility in all groups.
4.2.2.
Job Scheduling Algorithm
Using metrics
EC
J
and
ENR
, we propose a new job scheduling method called “expected-
credibility-based job scheduling”. Figure
??
shows the algorithm of the expected-
credibility-based job scheduling. First, all idle workers are stored in a worker queue (line
1 in Fig.
??
) and all unfinished jobs are grouped based on the value of
ENR
(line 2). Let
S
i
be the set of unfinished jobs of which
ENR
are equal to
i
. As long as the worker queue
is not empty, the master extracts a worker from the queue and allocates a job to the worker
(lines 6-23). When a worker
w
is extracted from the queue (line 8), by the spot-checking
mechanism, a spotter job is allocated to
w
with spot-check rate
q
. One unfinished job is
allocated to
w
if a spotter job is not allocated. In this case, the master creates a set of can-
didate jobs
CS
for job allocation (line 11).
CS
is a set of unfinished jobs of which
ENR
are less than
i + R
. Then, the master selects job
j
x
, which has a minimum
EC
J
(j)
in
CS
