## 4 DynDLOn: An Online Algorithm  
Existing data-parallel frameworks such as Hadoop and Spark typically use greedy approaches to handle online scheduling. For example, Hadoop's default scheduler tries its best to find a data-local task for each idle core. However, this heuristic and its variations such as delay scheduling [7] do not take the multicore servers into account, neglecting the fact that data-remote tasks on the same computer \begin{table}
\begin{tabular}{l l} \hline \hline
**Notation** & **Description** \\ \hline \(\mathcal{A}\) & task assignment \\ \(\mathcal{B}\) & balanced task assignment (see Section 4) \\ \(S\), \(P\), and \(T\) & server, core, and task sets \\ \(core(s)\) & set of cores that server \(s\) contains \\ \(sr(p)\) & server that contains core \(p\) \\ \(DL^{err}(t)\) and \(DL^{core}(t)\) & servers and cores that \(t\) prefers \\ \(g_{s}(n)\) & server \(s\)’s data-remote cost function; \(n\) is the number of data-remote tasks on \(s\) \\ \(L_{\mathcal{A}}(p)\) & load of core \(p\) \\ \(L^{init}(p)\) & initial load of core \(p\) \\ \(F_{\mathcal{A}}(t)\) & finish time of task \(t\) \\ \(r_{\mathcal{A}}^{s}\) and \(r_{\mathcal{A}}^{p}\) & numbers of data-remote tasks on server \(s\) (and core \(p\)) \\ \(l_{\mathcal{A}}^{s}\) and \(l_{\mathcal{A}}^{s}\) & numbers of data-local tasks on server \(s\) (and core \(p\)) \\ \(\textit{makespan}(\mathcal{A})\) & makespan of task assignment \(\mathcal{A}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Frequently used notations. compete for limited network bandwidth. In the following example, we illustrate how Hadoop's default scheduling policy and delay scheduling work. Table 2 shows a scheduling instance that contains 4 servers, 8 cores, and 5 tasks. Each server \(s\)'s data-remote cost function is \(g_{s}(n)=1+0.5n\). Figure 2a,b respectively present examples of Hadoop's and delay scheduling's assignments. According to the initial loads, the first idle core is \(p_{21}\). Both Hadoop and delay scheduling assign a data-local task to \(p_{21}\). In this example, we assume the data-local task is \(t_{1}\). The second idle core is \(p_{12}\). Both Hadoop and delay scheduling assign a data-remote task \(t_{2}\) to \(p_{12}\). Unlike Hadoop, delay scheduling lets \(p_{12}\) be idle for a short period, because there are no data-local tasks for \(p_{12}\). Then, \(p_{11}\) becomes the third idle core. Hadoop and delay scheduling assign a data-remote task to \(t_{3}\) to \(p_{11}\). Because \(p_{12}\) and \(p_{11}\) are on the same server, \(t_{2}\)'s and \(t_{3}\)'s running time increase from \(1.5\) to \(2\). The fourth idle core is \(p_{21}\) again, because it has finished \(t_{1}\). Then, Hadoop and delay scheduling assign a data-local task \(t_{4}\) to \(p_{21}\). The fifth idle core is \(p_{22}\). Because \(p_{22}\) has no data-local task, delay scheduling holds off on \(p_{22}\) for a while. When \(p_{22}\) is delayed, \(p_{31}\) becomes idle. Then, because \(t_{5}\) is a data-local task of \(p_{31}\), delay scheduling assigns \(t_{5}\) to \(p_{31}\) and generates an assignment whose makespan is 3.25. However, Hadoop does not delay \(p_{22}\), and assigns a data-remote task to \(p_{22}\). It generates an assignment whose makespan is 3.5. From the example, we can see that the idea of delay scheduling is effective, increasing data locality and decreasing makespan. However, the original delay scheduling algorithm does not take the multicore servers into account. It assigns two data-remote tasks to server \(s_{1}\), so the data remote costs on \(s_{1}\) increase from 1.5 to 2, which may increase the overall makespan. To address this problem, our heuristic is to dynamically set the duration of delay according to the idle server's data-remote cost. Figure 2c illustrates our heuristic. When \(p_{11}\) is idle, the scheduler finds data-remote tasks existing on \(s_{1}\), and sets a longer delay to \(p_{11}\). Because \(p_{22}\) and \(p_{31}\) become idle when \(p_{11}\) is delayed, the scheduler does not assign the second data-remote task to \(s_{1}\).