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

Figure 21. Calculation of EC J (j) and ENR(j) .

Basic job scheduling methods for credibility-based voting are the random and round-
robin methods [23]. 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 mas-
ter. Although these job scheduling methods are simple, they are not efficient because they
do not take account of a job's progress.
Thus, we propose a new job scheduling method for credibility-based voting that can
consider the progress of each job to reduce the overhead and computation time T .We
define two novel metrics for each job: the expected credibility and the expected number
of results. Using these two metrics, the proposed scheduling method can select a proper
job to be executed prior to others, thereby achieving a reduction in the computation time
of a computation. The proposed method employs spot-checking with a constant rate q and
backtracking, as in credibility-based voting [23].

4.2. Expected-Credibility-Based Job Scheduling

4.2.1. Definitions of Expected Credibility

To select a job for prior execution, it is important to consider the progress of each job.
The simple metric to represent the progress might be the credibility of the job because a
job is finished when the credibility of the job reaches threshold θ . However, this metric is
insufficient to grasp the proper progress because there might be several workers who are
engaged simultaneously in the execution of the job. Consider the case in which job j is
allocated to several workers, as shown in Fig.21. According to eq.(14), C J (j) is calculated
from the credibility of returned results. In the calculation, the workers who are currently
executing job j are not examined ( w 1 ,...,w d in Fig.21). Those workers will return their
results, which affect C J (j) ; therefore, the consideration of such workers is necessary to
grasp the proper progress of jobs.
Based on the idea described above, we define two new metrics for each job: the ex-
pected number of results and the expected credibility. Presuming that job j has several
results which can be grouped into G 1 ,...,G g and presuming that there exist d workers
( w 1 ,...,w d ) who are executing job j as shown in Fig.21, then the expected number of re-
sults and the expected credibility of job j , denoted by ENR(j) and EC J (j) respectively,
are defined as follows.