## 5 DynDLOff: An Offline Algorithm
### Phase I: Assign Data-Local Tasks
```
Input: Servers \(S\), Cores \(P\), Tasks \(T\), Data Placement \(DL^{srv}\) Output: Balanced Assignment \(\mathcal{B}\) // Generate a data-local assignment \(\mathcal{B}_{0}\)
1 foreach\(t\in T\)do
2\(\mathcal{B}_{0}(t)\leftarrow\operatorname*{argmin}_{p\in DL^{srv}(t)}\{L^{ init}(p)+l_{\mathcal{B}_{0}}^{p}\}\) // Build a bipartite graph and eliminate cost-reducing paths
3 Build a bipartite graph \(G\) according to \(\mathcal{B}_{0}\)
4 Compute \(MAX_{\mathcal{B}_{0}}^{srv}(s)\) and \(MIN_{\mathcal{B}_{0}}^{srv}(s)\) for each server \(s\)
5\(DONE\leftarrow\emptyset\)
6\(i\gets 0\)
7 while\(|DONE|\
eq|S^{\prime}|\)do
8\(s_{max}\leftarrow\max_{s\in S^{\prime}\wedge g\in DONE}MAX_{\mathcal{B}_{i}}^{ srv}(s)\)
9\(S_{visited}\gets DepthFirstSearch(G,s_{max})\)
10\(s_{min}\leftarrow\) the minimal load server in \(S_{visited}\)
11 if\(MAX_{\mathcal{B}_{i}}^{srv}(s_{max})-MIN_{\mathcal{B}_{i}}^{srv}(s_{min})>1\)then
12 Reverse the directions of \(arc(s_{max},t_{1}),\cdots,arc(t_{j},s_{min})\)
13 Update \(MAX_{\mathcal{B}_{i+1}(s)}^{srv}\) and \(MIN_{\mathcal{B}_{i+1}(s)}^{srv}\) for each server \(s\)
14\(i\gets i+1\)
15 else
16\(DONE\gets DONE\cup\{s_{max}\}\)
17 Generate a balanced assignment \(\mathcal{B}\) based on the bipartite graph
18 return\(\mathcal{B}\)
```  
**Algorithm 2**DynDLOff: Assign Data-Local Tasks (Phase I). The bipartite graph contains a task vertex set \(VT\) and a server vertex set \(VS\), such that for each task \(t\) there is a \(v(t)\in VT\) in the bipartite graph. Moreover, for each server \(s\in\bigcup_{t\in T}DL^{srv}(t)\), there is a \(v(s)\in VS\). The data placement strategy decides how the task vertices and server vertices are connected. For each \(s\in DL^{srv}(t)\), if \(s=\mathcal{B}_{0}(t)\), then there is a directional edge \(arc(s,t)\) connecting two  
Figure 3: Key steps of Phase I.  
vertices \(v(s)\) and \(v(t)\). Otherwise, edge \(arc(t,s)\) connects \(v(t)\) and \(v(s)\). Figure 2(b) shows a bipartite graph that corresponds to the initial assignment \(\mathcal{B}_{0}\). On the bipartite graph, we define an alternating path to be a sequence of edges \(Path=\{arc(s_{1},t_{1}),arc(t_{1},s_{2}),arc(s_{2},t_{2}),\cdots,arc(t_{k-1},s_{ k})\}\), with \(v(t_{i})\in TV\) and \(v(s_{i})\in SV\) for each \(i\). The cost-reducing path is a special case of an alternating path, holding that \(MAX^{svv}_{\mathcal{B}_{i}}(s_{1})-MIN^{svv}_{\mathcal{B}_{i}}(s_{k})>1\), where  
\[MAX^{svv}_{\mathcal{B}_{i}}(s) =max_{p\in core(s)}L_{\mathcal{B}_{i}}(p),\] \[MIN^{svv}_{\mathcal{B}_{i}}(s) =min_{p\in core(s)}L_{\mathcal{B}_{i}}(p).\]  
In Figure 2(b), the shadowed path from \(s_{4}\) to \(s_{1}\) is a cost-reducing path, because \(MIN^{svv}_{\mathcal{B}_{0}}(s_{1})=L_{\mathcal{B}_{0}}(p_{12})=0.5\) and \(MAX^{svv}_{\mathcal{B}_{0}}(s_{4})=L_{\mathcal{B}_{0}}(p_{41})=3.5\). Having a cost-reducing path, we flip the direction of each edge on the path to produce a new task assignment. Figure 2(c) shows a new bipartite graph after we flip the edge directions. After reversing edge directions, the algorithm produces a better task assignment \(\mathcal{B}_{i+1}\) such that \(\mathit{makespan}(\mathcal{B}_{i+1})\geq\mathit{makespan}(\mathcal{B}_{i})\). The bipartite graph that Figure 2(c) shows corresponds to a task assignment, where \(t_{5}\), \(t_{3}\), and \(t_{1}\) are assigned to \(s_{3}\), \(s_{2}\), and \(s_{1}\), respectively. The new task assignment's makespan is \(3.25\). The second step continuously finds the cost-reducing paths to improve the task assignment until no cost-reducing path can be found. To detect a cost-reducing path, we first select a max-load server \(s_{max}\) and then perform a depth-first search starting from \(v(s_{max})\) to traverse the bipartite graph. Among all the visited server vertices, the server vertex \(v(s_{min})\) is selected as the path's end, where \(s_{min}\) is the least-load server. If \(MAX^{svv}_{\mathcal{B}_{i}}(s_{max})-MIN^{sv}_{\mathcal{B}_{i}}(s_{min})>1\), we detect a cost-reducing path.