## 5 DynDLOff: An Offline Algorithm
### Phase II: Assign Data-Remote Tasks
Formally, given deadline \(D\), balanced assignment \(\mathcal{B}\), server \(s\), and load \(L_{\mathcal{B}}(p)\) for each core \(p\in\mathit{core}(s)\), this step is to compute the maximum number of data-remote tasks (i.e., \(r_{max}^{s}\)) that can be finished before \(D\). To compute \(r_{max}^{s}\), our algorithm checks all the possible values of \(r_{max}^{s}\) and selects the largest value. Suppose that a possible value is \(r_{i}^{s}\). Because the number of data-remote tasks is determined, we can compute the data-remote cost (i.e., \(g_{s}(r_{i}^{s})\)). Let \(\mathit{core}^{\prime}(s)\) be computer \(s\)'s cores whose loads are smaller than \(D\). The core can finish \(r_{i}^{s}\) data-remote tasks before \(D\) if and only if \(\sum_{p\in\mathit{core}^{\prime}(s)}\lfloor\frac{D-L_{\mathcal{B}}(p)}{g(r_{i} ^{s})}\rfloor>r_{i}^{s}\). To check all the possible values, a naive way is to set the number of data-remote tasks to \(1,2,\cdots,|T_{rem}|\) in turn. However, it is time-consuming because it needs to perform \(O(|T_{rem}|)\) tests. Our algorithm improves the complexity by exploring the upper and lower bounds of \(r_{max}^{s}\), which only requires \(O(\log|T_{rem}|)\) tests. **Theorem 1**. : _Let \(\Delta L_{\mathcal{B}}(s,D)=\sum_{p\in\mathit{core}^{\prime}(s)}\{D-L_{ \mathcal{B}}(p)\}\) be the remaining capacity of server \(s\). If \(\gamma\) satisfies \(\gamma\cdot g(\gamma)\leq\Delta L_{\mathcal{B}}(s,D)<(\gamma+1)\cdot g(\gamma +1)\), then \(\gamma\geq r_{max}^{s}\geq\max\{\gamma-|\mathit{core}^{\prime}(c)|,0\}\)._  
**Proof. ** We prove \(\gamma\geq r_{max}^{s}\) by contradiction. If \(\gamma<r_{max}^{s}\), then \(\Delta L_{\mathcal{B}}(c,D)\geq r^{s}\cdot g(r_{max}^{s})\geq(\gamma+1)\cdot g (\gamma+1)\). This contradicts the assumption. Thus, \(\gamma\) is the upper bound of \(r_{max}^{s}\). Figure 4: Key steps of Phase II (the assignment is the best when \(|T_{rem}|\) is 1). Next, we prove \(r_{max}^{s}\geq\max\{\gamma-|core^{\prime}(s)|,0\}\). We derive that \(r_{max}^{s}=\sum_{p\in core^{\prime}(s)}[\frac{D-L_{B}(p)}{g(r_{max}^{s})}]\geq \sum_{p\in core^{\prime}(s)}[\frac{D-L_{B}(p)}{g(\gamma)}]\geq\sum_{p\in core ^{\prime}(s)}\{\frac{D-L_{B}(p)}{g(\gamma)}-1\}=\frac{\Delta L_{B}(s,D)}{g( \gamma)}-|core^{\prime}(s)|\geq\gamma-|core^{\prime}(s)|\). Because \(r_{max}^{s}\geq 0\), we have \(r_{max}^{s}\geq\max\{\gamma-|core^{\prime}(s)|,0\}\). To compute \(\gamma\) (i.e., the upper bound of \(r^{s}\)), we precompute a matrix \(\mathbf{R}\) such that \(\mathbf{R}[s][i]=i\cdot g_{s}(i)\) for \(i=1,2,\cdots,|T|\). We then use a binary search to find \(\mathbf{R}[s][\gamma]\leq\Delta L_{B}(s,D)<\mathbf{R}[s][\gamma+1]\). Once \(\gamma\) is found, we test at most \(|core^{\prime}(p)|\) values. Overall, this step requires \(O(\log|T_{rem}|)\) tests, and its time complexity is \(O(\log|T|)\)  
**Computing final assignment. ** Let the assignment corresponding to \(\mathbf{D}[i]\) be \(\mathcal{A}_{i}\). We can 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+1\leq i\leq j\), \(\mathit{makespan}(\mathcal{A}_{k+1})\leq\mathit{makespan}(\mathcal{A}_{j})\). Thus, there are either \(k\) or \(k+1\) data-remote tasks in the final assignment. Although it is easy to compute \(\mathit{makespan}(\mathcal{A}_{k})\) (i.e., \(\mathbf{D}[k]\)), computing \(\mathit{makespan}(\mathcal{A}_{k+1})\) is non-trivial, because \(\mathit{makespan}(\mathcal{A}_{k+1})\) does not equal \(\mathbf{D}[k+1]\) and we need to find an assignment with the smallest makespan. Our solution contains two steps. First, we compute the total number of data-remote tasks that are completable before \(\mathbf{D}[k+1]\). Suppose server \(s\) can finish \(r^{s}\) data-remote tasks before \(\mathbf{D}[k+1]\), then in total, \(\sum_{s\in S}r_{max}^{s}\) data-remote tasks are completable before \(\mathbf{D}[k+1]\). Second, we assign the remaining \((k+1)-\sum_{s\in S}r_{max}^{s}\) data-remote tasks by using a max-min scheduling policy.