## 4 Algorithm Description
### The Deadline Preference Dispatch Scheduling (DPDS) Algorithm
```
Input: the task \(t^{\prime}\), volunteer node set \(N_{l}\), the current time \(l\) Output: task assignment set \(t\).assign
1. Initialize \(t^{\prime}\).assign = \(\emptyset\); \(t^{\prime}\).remain = \(t^{\prime}\).cost; \(t^{\prime}\).hasassign = 0
2. total_ability = the total computing power of the set \(N_{l}\) at time \(l\)
3. While\(t^{\prime}\).remain >0&t&t'.deadline \(l\)do//\(t^{\prime}\).remain indicates the remaining unallocated workload of \(t^{\prime}\)
4. If\(t^{\prime}\).remain >= total_ability
5. For each node \(n^{\prime}\) in \(N_{l}\)do add \(<n^{\prime}\), \(t^{\prime}\), \(l>\) to \(t^{\prime}\).assign
7. Delete \(n^{\prime}\) from \(N_{l}\)
8. End For
9. \(t^{\prime}\).remain = \(t^{\prime}\).remain - total_ability
10. \(L=l+1\)// all nodes have been assigned to calculate \(t^{\prime}\) at time \(l\)
11. Reset \(N_{l}\) / node set at time \(l+1\)
12. Else
13. \(j=1\)
14. While the \(j\)th node \(n^{\prime}\) in \(N_{l}\) is not null do
15. If\(n^{\prime}\).ability <= \(t^{\prime}\).remain  add \(<n^{\prime}\), \(t^{\prime}\), \(l>\) to \(t^{\prime}\).assign
17. Delete \(n^{\prime}\) from \(N_{l}\)
18. \(t^{\prime}\).remain = \(t^{\prime}\).remain -\(n^{\prime}\).ability;
19. Else\(t^{\prime}\).remain == 0
20. \(t^{\prime}\).cost = 0
21. Return \(t^{\prime}\).assign
22. Else
23. While\(n^{\prime}\).ability >= \(t^{\prime}\).remain&t&n' is not null do
24. \(j=j+1\)
25. \(n^{\prime}\) = the _jth_ node in \(N_{l}\)
26. Endwhile
27. \(n^{\prime}\) = the \((j-1)\)th node in \(N_{l}\)
28. add \(<n^{\prime}\), \(t^{\prime}\), \(l>\) to \(t^{\prime}\).assign
29. Delete \(n^{\prime}\) from \(N_{l}\)
30. \(t^{\prime}\).cost = \(t^{\prime}\).remain = 0;
31. EndIf
32. EndIf
33. EndWhile
34. Return \(t^{\prime}\).assign

### The Improved Dispatch Constrain Scheduling (IDCS) Algorithm

The DPDS algorithm is a deadline priority allocation method, which can ensure that the most urgent tasks are given the highest priority in dynamic allocation. However, it cannot guarantee the largest number of tasks to be completed. And we find that the task cannot be completed within deadline constraint is still assigned, which causes a waste of computing resources. On this basis, this paper proposes an improved IDCS algorithm. The IDCS algorithm uses a risk prediction model to reduce the waste of computing resources. Before introducing the IDCS algorithm, we introduce the risk prediction model firstly. #### 4.2.1 The Risk Prediction Model

In this paper, we propose a risk prediction model that can predict the **completion risk** of each task, which is described in Algorithm 3. In VC platforms, VN is constantly updated at every moment. Although, it is impossible to accurately determine the number of updated nodes and their computing power, the range of the number of possible online nodes at each time can be estimated based on historical data. For easy calculation, we assume that the computing power of all predicted online VN is 1 unit, and the probability of the number of possible VN at each time is the same. On this basis, we calculate the **completion risk** of each task by **completion probability**. We will introduce the definition of the **completion probability** below. **Definition 3** (Completion probability): _Given a possible world [30] set \(W\) and a task \(t^{\prime}\) at time \(l\), the **completion probability** of \(t^{\prime}\) at time \(l\) is defined as follows:_

\[\Pr^{l}(t)=\sum_{w\in W^{\prime}}\Pr(w), \tag{1}\]

_where \(w\) represents a possible world in a possible world set \(W\), \(W^{\prime}\) is a possible world set which is composed of a possible world that can complete \(t^{\prime}\) within the deadline, and Pr(\(w\)) represents the **possible probability** of \(w\)._

For example, at time \(l_{1}\), the task \(t_{6}\) is allocated at time \(l_{1}+3\), and the deadline of \(t_{6}\) is \(l_{1}+4\). Figure 5a shows that the number of possible VN at time \(l_{1}+3\) is 3, 4, and 5, and the number of possible VN at time \(l_{1}+4\) is 3, 4, and 5.