SABOTAGE-TOLERANT JOB SCHEDULING FOR RELIABLE VOLUNTEER COMPUTING - Computer Science Research and Technology - page 150

scheduling cost for the proposed method, i.e. Cost prop (t) , is calculated as
Cost prop (t)=(1− q)(t c +2(t c + t e )) + qt(t c +(t c + t e ))
= Cost orig (t)+(t c + t e )(2(1 − q)+qt). (21)
By definition, the time to calculate EC J is almost identical as t c (the time to calculate C J ).
The average of Cost prop (t) , i.e. E(Cost prop ) , is given as the following.

T X

E(Cost prop )= 1
T

Cost prop (t)

t=1

=2× t c ((1 − q)+ q(T +1)
2

)+t c (1 − q)

+t e (2(1 − q)+ q(T +1)
2

). (22)

The value of q is between 0 and 1 and T>>1 (several orders of magnitude). Therefore,
the second term in eq.(22) is negligibly small compared to the first. The third term in
eq.(22) is also negligibly small compared to the first because calculation of ENR involves
the simple addition shown in eq.(17), then t e is negligibly small. Therefore, E(Cost prop )
can be represented as follows.

E(Cost prop ) ≈ 2 × E(Cost orig ). (23)

From eqs. (20) and (23), it is apparent that the scheduling costs of both methods are negligi-
bly small compared to the execution time of a job in general VC systems (e.g. several hours
in [11]), because t c , the calculation cost of one credibility, is a very small value (on the order
of microseconds). Furthermore, both scheduling costs (for a single worker) are independent
of the system scale, such as the number of jobs and the number of workers. Consequently,
both methods will work well in large-scale VC systems, without a considerable increase in
the workers' waiting time.

4.3. Performance Evaluation

4.3.1. Simulation Conditions

We evaluate the effectiveness of the proposed job scheduling method through the simula-
tion of VCs. Computation times T and error rates of VCs are evaluated as the average
of 100 simulation results for different job scheduling methods: random (denoted by “ran-
dom”), round robin (denoted by “rr1”) [23], and several variants of the proposed method.
The variants of the proposed method select jobs using ENR and EC J . They are called,
respectively, “ ENR method” and “ EC J method”.
• ENR method:
This method selects a job that has a minimum ENR in all unfinished jobs. A round-
robin selection is used if some jobs have the same ENR .

• EC J method
This method selects a job that has a minimum EC J in the candidate jobs CS . De-
pending on the value of R , i.e. how to create CS , there are several variants of EC J
method.