# Exploiting Duplications for Efficient Task Offloading in Multi-User Edge Computing
## 5 The DETO Algorithm in the Ultra-Dense Network  
The explosive number of users in the edge network is challenging for the most advanced fourth-generation network. Furthermore, the ultra-dense network has been considered as a promising candidate for future 5G networks to meet this explosive user demand. The basic idea is to have multiple servers as close as possible to the end users. Furthermore, each user can offload their tasks to either one of them according to the condition of each server (such as the channel condition and the computation load of a server). However, considering the high dynamic characteristics of the edge scenario, each user has little information about others. Thus, the user cannot estimate the wireless communication rate and the execution time in the server according to Equations (6) and (7). To overcome this dilemma, we use the centralized DETO algorithm in the ultra-dense network (as shown in the Algorithm 3):In the centralized DETO scheme, we first enumerate all the possible offloading strategies and then call the DETO algorithm to obtain the subtask scheduling and duplication scheme under a certain offloading strategy. In _line_ 4, we integrate the task of graphs of the users that offload to the same server, and thus the input of Algorithm 1 will be a large DAG, which consists of a series of disconnected subgraphs, and it is impossible for us to find a critical path as shown in _Listing Phase_. Thus, we need to propose a new metric to order the subtasks. \[rank(i,j)=\overline{t_{i,j}}+\max_{l\in succ(j)}\{rank(i,l)+\overline{C_{l,j}}\} \tag{16}\]  
The \(rank(i,j)\) is the length of the critical path from task \(j\) to the exit task. The higher the value is, the higher the priority. For example, in Figure 2, the rank of each node is as follows: rank(a) = 10, rank(b) = 8, rank(c) = 5, rank(d) = 6, rank(c) = 1. In this way, we can rank all the subtasks from the different disconnected subgraphs. Theorem 4.1: _The computational complexity of centralized DETO in Algorithm 3 is no less than \(O[(S+1)^{N}\cdot(n+2e)]\), where \(S\) and \(N\) are the numbers of edge servers and IoT devices, respectively. \(n\) and \(e\) denote the number of subtask and the edge of DAG._  
Proof: We assume that there are S users who need to offload their tasks to the edge network, which consists of N edge servers. The number of possible optional offloading strategies are:  
\[(^{0}_{N})\cdot S^{0}+(^{1}_{N})\cdot S^{1}+\ldots\ldots(^{N}_{N})\cdot S^{N}= \sum_{i=0}^{p}(^{p}_{N})\cdot S^{p} \tag{17}\]  
where \(p\) denotes the number of users who decide to offload their tasks. According to [PERSON]'s binomial theorem:  
\[\sum_{i=0}^{i}(^{p}_{N})\cdot S^{p}=(S+1)^{N} \tag{18}\]  
Each potential offloading strategy needs to invoke the DETO algorithm to obtain the server scheduling result and its computation delay. The time complexity of the first part in DETO is \(O(n+2e)\), and the time complexity of the second step in DETO is \(O(n)\). Therefore, the computational complexity of centralized DETO is no less than \([O(S+1)^{N}\cdot(n+2e)]\). From Theorem 4.1, we find that the centralised DETO algorithm would cause considerable overhead with the increasing number of users and edge servers, as it always enumerates all the optional offloading decisions. Even worse, it would possibly lead to system failure if the centralized controller were involved in hardware failure. In this section, we adopt a game-theoretic approach to address such a challenge. Game theory is a useful framework for designing decentralized scheme, such that user devices in the edge network can self-organize into mutually satisfactory computation offloading and duplication decisions. In the game-theory-based offloading and duplication strategy in the ultra-dense network, the user can make the decision locally according to the information broadcast by the edge server at each step and make an optimal local decision. After finite steps, none of the users can further improve its execution time by changing its offloading and duplication strategy unilaterally.