## 4 Algorithm Description
### The Deadline Preference Dispatch Scheduling (DPDS) Algorithm  
The DPDS algorithm is a dynamic task scheduling algorithm based on deadline constraint priority. Firstly, the DPDS algorithm sorts the tasks in ascending order according to their deadline and sorts the VN in descending order according to their computing power. Secondly, the DPDS algorithm adopts a matching function to select the most suitable volunteer node to assign a task, which make the computing resource will be freed in the least possible amount of time. Consequently, the DPDS algorithm can ensure that the task with nearest deadline constraint is completed first, and free computing resource in the least possible amount of time. The DPDS algorithm is described in detail in Algorithm 1. Significantly, in the DPDS algorithm, we use a monitoring mechanism, which is triggered to meet the following two conditions simultaneously. * The volunteer computing platform has been running for an hour. * There are new nodes or tasks arrived at the VC platform. ```
Input: task set \(T_{l}\), volunteer nod set \(N_{l}\), the current time \(l\) Output: final task assignment set \(T\).\(\mathit{assign}\). 1. Wait until the monitoring mechanism is trigged
2. \(\mathit{Tassign}=\emptyset\)
3. Sort \(T_{l}\) in ascending order according to the task's deadline at time \(l\)
4. Sort \(N_{l}\) in descending order according to the node's computing power at time \(l\)
5. \(\mathit{While}\)\(T_{l}\
eq\emptyset\)do
6. Take the first task from \(T_{l}\) to \(t\)'
7. Call the \(\mathbf{match(\textit{t}^{\prime},\textit{N}_{l},\textit{D})}\) // select the most suitable volunteer node to \(t\)'
8. Delete \(t\)' from \(T_{l}\)
9. \(\mathit{Tassign}=\mathit{Tassign}+\textit{t}^{\prime}.\mathit{assign}\)
10. End While
11. Return\(\mathit{Tassign}\)
```  
**Algorithm 1**The DPDS Algorithm Taskassign(\(T_{l}\),\(N_{l}\),\(\textit{D}\))  
If the monitoring mechanism is triggered, to make full use of the computing resources provided by the idle VN, we adopt the match function to select the suitable VN that wastes the least amount of computing resources in the DPDS algorithm. The match function is described in detail in Algorithm 2. For example, the list of tasks at time \(l_{1}\) is shown in Figure 1(a) and list of volunteer nodes at time \(l_{1}\) is shown in Figure 1(b). According to the first to fourth lines of Algorithm 1, at time \(l_{1}\), \(T_{1}=\{t_{1},t_{2},t_{3},t_{4}\)  
Figure 3: Task list and volunteer nodes list at time \(l_{1}+1\). (**a**) List of tasks at time \(l_{1}+1\); (**b**) list of volunteer nodes at time \(l_{1}+1\). \(t_{5}\)], \(\text{N}_{\text{l}}=\{n_{1},\,n_{2},\,n_{4},\,n_{6},\,n_{5},\,n_{3}\}\). Take \(t_{1}\) as an example, according to the sixth line of Algorithm 1, it can be seen that \(\text{t}_{1}\) is allocated first. According to Algorithm 2, at time \(l_{1}\), \(t_{1}\)_assign_ = \(\{(n_{1},\,t_{1},\,l_{1}),\,(n_{2},\,t_{1},\,l_{1}),\,(n_{3},\,t_{1},\,l_{1}),\,(n_{4 },\,t_{1},\,l_{1}),\,(n_{5},\,t_{1},\,l_{1}),\,(n_{6},\,t_{1},\,l_{1})\}\). As can be seen from the task assignment above, there is still 1.5 units left in task \(t_{1}\), which needs to be allocated at time \(l_{1}+1\). At time \(l_{1}+1\), both the task list and the node list are updated, which are shown in Figures 3a and 3b, so the monitoring mechanism is triggered. According to the first to fourth lines of Algorithm 1, at time \(l_{1}+1\), \(\text{T}_{1}=\{t_{1},\,t_{6},\,t_{2},\,t_{3},\,t_{4},\,t_{5}\}\), \(\text{N}_{\text{l}}\) = \(\{n_{1},\,n_{4},\,n_{7},\,n_{6},\,n_{5},\,n_{3}\}\). According to the sixth line of Algorithm 1, it can be seen that \(t_{1}\) is allocated first. According to Algorithm 2, at time \(l_{1}+1\), \(t_{1}\)_assign_ = \(\{(n_{1},\,t_{1},\,l_{1}+1),\,(n_{3},\,t_{1},\,l_{1}+1)\,\}\). By analogy, we assume that tasks and nodes are updated only at time \(l_{1}+1\), so the rest of the task assignments are shown in Figure 4. Figure 4 shows \(t_{3}\) and \(t_{5}\) cannot be completed within the deadline.