## 4 Algorithm Description
### The Deadline Preference Dispatch Scheduling (DPDS) Algorithm
Return \(\mathit{Tassign}\)
```

**Algorithm 4**The IDCS Algorithm

For example, the list of tasks at time \(l_{1}\) is shown in Figure 1(a), and the list of volunteer nodes at time \(l_{1}\) is shown in Figure 1(b). List of tasks at time \(l_{1}+1\) is shown in Figure 2(a), and the list of volunteer nodes at time \(l_{1}+1\) is shown in Figure 2(b). For the easy calculation, we assume that the nodes and tasks are not updated at other times, and the value of \(\theta\) is 0.5. The **completion risk** of \(t_{3}\) is 0.67 according to Algorithm 3, which is assigned at time \(l_{1}+3\). According to Algorithm 4, \(t_{3}\) is deleted from the task set \(T_{l}\). According to Algorithm 1, the assignment of the remaining tasks is shown in Figure 7. According to the task allocation of Figure 7, the tasks can be completed within deadline constraint are \(t_{1}\), \(t_{2}\), \(t_{4}\) and

Figure 6: Task classification and corresponding priority. \(t_{5}\). Figure 7 shows that the IDCS algorithm can maximize the number of the completed tasks within deadline constraint. ## 5 Experimental Evaluation

In this section, we first implement the DPDS algorithm and the IDCS algorithm, and use static task set and dynamic task set to compare the performance between the MOC algorithm and our proposed algorithms. The volunteer computing used in the experiment consists of one master node and fifty volunteer nodes. All nodes are configured with Intel Core i7 4790 [EMAIL_ADDRESS] GHZ, 8 GB DDR3 memory, 1 TB hard disk and Windows 10 operating system. To be closer to the real volunteer computing environment and meet the heterogeneity of volunteer computing, 10-20 threads are opened on each host to simulate volunteer nodes, thus, whose number will be between 500 and 1000. Task data fragmentation size is 64 MB, and the parameter \(n_{j}\)_ability_ is tested by the server sending the applet to the node before assigning tasks. Specifically, to achieve the heterogeneity of nodes, we use a program to specify different CPU cores for some specific threads. In this way, scheduling delays can be reduced by specifying the CPU core for some specific threads. Thus, the performance of some specific threads will be improved. ### Experimental Results and Analysis of the Static Task Sets

In the experiment of the static task set, three common tasks are used: Word frequency statistics, inverted index and distributed Grep. The input files are the data and dump files provided by Wikipedia (the main contents are entries, templates, picture descriptions and basic meta-pages, etc.). We mainly consider the influence of three main parameters as follows:

* The task set scale which is the number of tasks included in the task set \(T\). * The average size of tasks in task set \(T\) is measured by the number of task input file fragments. * The average completion time of tasks in \(T\). We assume that the size of a task set fragment is 64 MB, the threshold \(\theta\) is 0.5 and the completion time of each task fragment is 70 s. The task amount of word frequency statistics for a fragment (unit) is 40 s, the task amount of inverted index for a fragment (unit) is 80 s, and the task amount of distributed Grep for a fragment (unit) is 120 s. The average completion time of the tasks in \(T\) is 80 s, denoted by \(L\). For any task in \(T\), \(t\). _deadline_ is a random value in the interval [0.5L, 1.5L]. Table 2 shows the default values and ranges of the main parameters. Table 2 shows the default values and ranges of the main parameters. Figure 7: The execution processes of the improved dispatch constraint scheduling (IDCS) algorithm. In this paper, the number of the completed tasks is the primary performance index. In addition, this paper also uses the completion rate to measure the performance of the algorithm more comprehensively.