Information Technology Reference
In-Depth Information
The results collected for a job are grouped into several result groups,
G
1
,...,G
g
, each
of which includes all results having the same value. The credibility of a result group
G
a
(denoted by
C
G
(G
a
)
) is given by eq.(11).
Q
P
T
(G
a
)
i6=a
P
F
(G
i
)
C
G
(G
a
)=
i6=n
P
F
(G
i
)
,
(11)
Q
P
Q
g
g
i=1
P
F
(G
i
)+
n=1
P
T
(G
n
)
where
P
T
(G
a
)
and
P
F
(G
a
)
are given as follows;
Q
P
T
(G
a
)=
r∈G
a
C
R
(r),
(12)
Q
P
F
(G
a
)=
r∈G
a
(1 − C
R
(r)).
(13)
Therein,
P
T
(G
a
)
(
P
F
(G
a
)
) is the probability that all results in
G
a
are correct (incorrect).
In eq.(11),
C
G
(G
a
)
represents the conditional probability that the results in
G
a
are correct
and those in all other groups are incorrect, for a given combination of the result groups.
The credibility of a job
j
(denoted by
C
J
(j)
) is equal to
C
G
(G
x
)
, where
G
x
is a result
group that has a maximum credibility among all result groups for job
j
.
C
J
(j)=C
G
(G
x
)=max
1≤a≤g
C
G
(G
a
).
(14)
When
C
J
(j)
reaches threshold
θ (= 1 −
acc
)
, the result of the group
G
x
is accepted as
the final result of job
j
; then job
j
is finished.
3.2.
Performance Evaluation
3.2.1.
Simulation Conditions
In this section, we evaluate sabotage-tolerance performance and study the drawbacks of
current sabotage-tolerance methods such as
M
-first voting through the simulation of VCs.
Computation times
T
and error rates of VCs are evaluated as the average of 100 simu-
lation results. The random (denoted by “random”) and the round-robin (denoted by “rr1”)
methods are used as basic job scheduling methods. The random method selects a job at
random and the round-robin method selects a job in a static order, e.g. the order of a job's
ID assigned by the master.
The parameters used in our simulation are shown in Table 1. Because some parameters
are unknown to the master and are uncontrollable, such as
f
,
s
and
c
, we use variant values
for such parameters to simulate various cases of VCs. The upper limit of
f
, i.e.
f
max
, is set
to 0.35 reflecting the result of an experiment in a real VC environment [27]. Because the
optimal value of
q
depends on
f
and
s
[38, 39],
q
is set to
0.1
or
0.2
as in [23, 40].
The simulator developed for this experiment follows that in [23, 40]. At the start of each
iteration of simulation, we create a list of
W
worker entries and randomly select
f × W
workers to be saboteurs. We then simulate a computation done by these workers by going
through the list in round-robin manner. In each unit time (called “turn”), a worker contacts
the master to return a result (for the job it received in the previous turn) and get a new job.
This assumes that all workers run at the same speed. To support this approach and generate a
stream of pseudo-random numbers, we employ the method Math.random() in Java library,
which uses a 48-bit seed and a linear congruential formula [37].
We also assume that a
