# Exploiting Duplications for Efficient Task Offloading in Multi-User Edge Computing
## 3 System Model
### Processor Selection Phase  
After we obtain the priority of each subtask, we need to schedule them and their duplication on its \"best\" processor. The duplication-based task offloading scheme is described in Algorithm 1. Before that, we give the definition of the _Critical Predecessor_ (CP). According to Equation (5), the subtask start time depends on the data arrival time of the predecessor task. Furthermore, the predecessor task from which the data arrives at the latest time is defined as the critical predecessor (CP).  
\begin{table}
\begin{tabular}{c c c} \hline \hline  & **Earliest Start Time** & **Earliest Finish Time** \\ \hline Node \(a\) & 0 ms & 0 ms \\ \hline Node \(b\) & 2 ms & 3 ms \\ \hline Node \(c\) & 6 ms & 6 ms \\ \hline Node \(d\) & 3 ms & 5 ms \\ \hline Node \(e\) & 10 ms & 10 ms \\ \hline \hline \end{tabular}
\end{table}
Table 3: Earliest start/finish time.  
Figure 2: Subtask list algorithm.  
```
1. Sort all the subtasks in DAG into a \(Rank_{list}\) by increasing the order of their rank
2. **while** there are unscheduled subtasks in the \(Rank_{list}\)
3. select the first unscheduled subtask \(T_{i,j}\) in \(Rank_{list}\);
4. Let \(E_{t}=\infty\);
5. **For** each process \(S_{1}\) in \(S\)
6. compute the \(t_{i,j,s_{1}}^{F}\) without duplication
7. **if**\(t_{i,j,s_{1}}^{F}<E_{t}\)
8. \(E_{t}=t_{i,j,s_{1}}^{F}\), save scheduling result to \(P\)
9. **endif;**
10. Let \(T_{i,l}=CP(T_{i,j})\)
11. **For** each processor \(S_{2}\) in \(S\)
12. recompute \(t_{i,j,s_{1}}^{F}\) while duplicating \(T_{i,l}\) on \(S_{2}\)
13. **if**\(t_{i,j,s_{1}}^{F}<E_{t}\)
14. \(E_{t}=t_{i,j,s_{1}}^{F}\), save scheduling result to \(P\)
15. Recompute the \(T_{i,l}=CP(T_{i,j})\)
16. **Goto**\(line12\)
17. **endif**
18. **end For**
19. **end For**
20. Schedule \(T_{i,j}\) according to the scheduling result \(P\)
21. **Mark**\(T_{i,j}\) as scheduled
22. **end while**
```  
**Algorithm 1** The duplication-based task offloading algorithm.  
In the algorithm, there are three nested loops: (1) In the first loop (step from 2 to 22), all the subtasks and possible duplications will be assigned and scheduled by order of increasing rank value. (2) The second \"for loop\" (step from 5 to 19) is to consider each processor in \(P\) as a potential processor to which the subtask \(T_{i,j}\) could be scheduled and will find the \"best\" processor that minimizes its finish time. (3) Inside the second loop, the third loop (step from 11 to 17) introduces the task duplication into the algorithm. In \(line\) 12, we duplicate the critical predecessor of \(T_{i,j}\) on each processor to see whether the finish time of \(T_{i,j}\) can be further reduced.  
Since the critical predecessor is the one from which data will be received the latest by \(T_{i,j}\), duplicating other predecessor tasks other than the CP will not decrease the finish time of \(T_{i,j}\). In addition, if the duplicate the CP of \(T_{i,j}\) will reduce the finish time of \(T_{i,j}\), the duplication decision and scheduling result will be saved to \(P\). After the duplication operation, the previously critical node may not be the latest one that transfers the date to the \(T_{i,j}\). Thus, in \(line\) 14 and \(line\) 15, we recompute the critical predecessor and return back the third loop attempt to further reduce the finish time of \(T_{i,j}\) by replicating the new critical predecessor.