# Exploiting Duplications for Efficient Task Offloading in Multi-User Edge Computing
## 3 System Model  
In our offloading scenario, there are a certain number of heterogeneous servers in the edge network, defined by \(\mathcal{M}=[1,2,\ldots,m,\ldots,M]\). We consider a set of \(\mathcal{N}=[1,2,\ldots,i,\ldots,N]\) user. Each user has a task to be offloaded to the edge network. The execution procedure of the application of user \(i\) can be represented by directed acyclic graphs (DAGs) \(G_{i}=(V_{i},E_{i})\), where \(V_{i}=[T_{i1},T_{i2},\ldots,T_{ij},\ldots,T_{ie}]\) denotes the set of subtasks to be executed, and \(T_{ij}\) denotes the possible duplication of \(T_{ij}\).  
\(E_{i}\) represents the set of directed edges characterizing the dependency between the subtasks, and the weight of each edge \(edge_{jk}\) represents the amount of data communication between subtasks, in which the subtask \(j\) is one of the immediate predecessors of subtask \(k\). Our problem is to upload and schedule these subtasks and the possible duplication of them from different users on edge servers to minimize the overall completion time of all the applications. A feasible schedule should satisfy the following constraints:  
1. _Constraints on tasks_: Considering the low-power character of IoT devices, these devices are always equipped with only one radio. Thus, only one of the edge servers can be selected by an IoT device during the task execution. Furthermore, each subtask cannot be interrupted during the execution.
2. _Constraints on communication_: The subtask cannot start until all its immediate predecessors have been finished, and their results have been received. The transferring time is affected by the size of communication data and the communication rate if these two tasks are not assigned to the same processor.
3. _Constraints on processors_: The processors can only run tasks serially--that is to say, the execution of any two subtasks on the same processor cannot overlap. To facilitate the discussion, we assume that the IoT devices and the edge servers have only one processor.  
Since our target is to minimize the average completion time in a multi-user and multi-server edge network scenario under the energy-consumption constrain, the transmission time and the execution time should be considered at the same time. In this section, we first present the communication and execution model, and then we propose the energy-consumption model. Finally, we present our optimization problem. The notations used in this paper are summarized in Table 2.  
\begin{table}
\begin{tabular}{c l} \hline \hline
**Notation** & **Description** \\ \hline \(\mathcal{N}\) & The set of user \\ \hline \(\mathcal{M}\) & The set of edge servers \\ \hline \(\mathcal{V}_{i}\) & The set of subtasks of devices \(i\) \\ \hline \(T_{i,j}\) & The subtask \(j\) of the device \(i\) \\ \hline \(T_{i,j}\) & The duplication of \(T_{i,j}\) \\ \hline \(edge_{i,j}\) & The data communication from subtask \(i\) to subtask \(j\) \\ \hline \(d_{i}\) & The offloading scheme of device \(i\) \\ \hline \(d_{i,j}\) & The offloading strategy of subtask \(T_{i,j}\) \\ \hline \(\mathbf{D}\) & A possible offloading scheme of all subtasks in the edge \\ \hline \(Rate_{i,k}\) & The communication rate between device i and server \(k\) \\ \hline \(t_{i,j,k}\) & The execution time of \(T_{i,j}\) in processor \(k\) \\ \hline \(t_{i,j,k}^{D}\) & The time when all the data is ready for \(T_{i,j}\) \\ \hline \(t_{i,j}^{F}\) & The actual finish time of subtask \(T_{i,j}\) \\ \hline \(t_{i,j,k}^{S}\) & The actual starting time of subtask \(T_{i,j}\) \\ \hline \(C_{j,l}^{c}\) & Data exchange time between subtask \(j\) and subtask \(l\) \\ \hline \(t_{i,j}^{k}\) & The processor \(k\) is available to execute \(T_{i,j}\) \\ \hline \hline \end{tabular}
\end{table}
Table 2: Notations used in the paper.