## 5 DynDLOff: An Offline Algorithm
### Time Complexity and Optimality  
Here, we analyze DynDLOff's time complexity and optimality. DynDLOff assigns tasks in polynomial running time. Although it is an approximate algorithm, DynDLOff can find optimal assignments in certain specific instances. We first show the time complexities of DynDLOff's two phases. **Theorem 2**. : _Phase I's time complexity is \(O\big{(}|T|^{2}\big{)}\)._  
Proof. : The total time required to finish the first step is \(O(|T|)\), because every task is examined exactly once, and \(|DL^{sr}(t)|\) and \(|core(s)|\) are constants. The task assignment produced by the greedy approach satisfies Constraint 1 and roughly balances the cores' loads. Hence, the second step is to adjust the assignment to reach the optimal makespan. The total time required to finish the second step is \(O(|T|^{2})\). First, detecting a cost-reducing path costs \(O(|T|)\), because there are at most \(k|T|\) edges, where \(k\) is the maximum number of servers that a task prefers. Each cost-reducing path moves one unit of the load from the max-load to the min-load server. Because there are \(O(|T|)\) units of loads, the number of iterations for detecting cost-reducing paths is \(O(|T|)\). Overall, the second step's time complexity is \(O(|T|^{2})\). Combined with the first step's time, the time required to finish Phase I is \(O(|T|^{2})\). **Theorem 3**. : _Phase II's time complexity is \(O(|T|\log|T|+|S|\log^{2}|T|+|T|\log|S|)\)._  
**Proof. ** In Phase II, initializing \(\mathbf{T}\) and \(\mathbf{D}\) takes \(O(|T|\log|T|)\). To find a proper deadline, it tests \(O(\log|T|)\) deadlines. For each deadline, it takes \(O(|S|\log|T|)\) to determine whether the deadline passes the test, so it takes \(O(|S|\log^{2}|T|)\). To compute a final assignment, it uses a min heap to maintain the servers' loads. Building a min heap takes \(O(|S|)\), updating a min heap takes \(O(\log|S|)\), and there are \(O(|T|)\) updates, so it takes \(O(|S|+|T|\log|S|)\) to compute a final assignment. Overall, Phase II's time complexity is \(O(|T|\log|T|+|S|\log^{2}|T|+|T|\log|S|)\). Combining the two phases' time complexities, DynDLOff's time complexity is \(O(|S|\log^{2}|T|+|T|\log|S|+|T|^{2})\). Next, we prove that DynDLOff is optimal when the maximum load core only contains data-local tasks. Let \(\mathcal{O}\) be the optimal assignment, \(\mathcal{A}_{i}\) be an assignment generated by DynDLOff that contains \(i\) data-remote tasks, and \(\mathcal{A}_{k}\) be DynDLOff's output. We conclude \(\forall i\leq j\leq k\), \(\mathit{makespan}(\mathcal{A}_{i})\geq\mathit{makespan}(\mathcal{A}_{j})\geq \mathit{makespan}(\mathcal{A}_{k})\), and \(\forall k\leq i\leq j\), \(\mathit{makespan}(\mathcal{A}_{k})\leq\mathit{makespan}(\mathcal{A}_{i})\). Suppose \(\mathcal{O}\) contains \(n\) data-remote tasks. We have \(\mathit{makespan}(\mathcal{A}_{n})\geq\mathit{makespan}(\mathcal{A}_{k})\geq \mathit{makespan}(\mathcal{O})\). Theorem 4: _For the maximum load core \(p\) of assignment \(\mathcal{A}_{n}\) such that \(L^{\mathit{core}}_{\mathcal{A}_{n}}(p)=\mathit{makespan}(\mathcal{A}_{n})\), if \(p\) only executes data-local tasks, then \(\mathcal{A}_{n}\) is optimal._  
**Proof. ** Given a balanced assignment \(\mathcal{B}\), let \(\langle p_{1},p_{2},\cdots,p_{|S|}\rangle\) be a sorted list such that \(L^{\mathit{core}}_{\mathcal{B}}(p_{i})>L^{\mathit{core}}_{\mathcal{B}}(p_{i+1})\). Suppose that the maximum load core of \(\mathcal{A}_{n}\) is \(p_{u}\) (i.e., the \(u\)th core in the list). For sake of contradiction, assume that \(\forall p_{i}\in P_{i},L^{\mathit{core}}_{\mathcal{A}_{n}}(p_{u})>L^{\mathit{ core}}_{\mathcal{A}_{n}}(p_{i})\). We divide the cores into two groups: \(P_{u^{-}}=\{p_{i}|1\leq i\leq u\}\), \(P_{u^{+}}=\{p_{i}|u<i\leq|T|\}\). Let \(l_{u^{-}}(\mathcal{A})\) and \(l_{u^{+}}(\mathcal{A})\) denote the numbers of data-local tasks that \(\mathcal{A}\) assigns to \(P_{u^{-}}\) and \(P_{u^{+}}\), respectively.