## 4 DynDLOn: An Online Algorithm
As a result, the heuristic reduces the number of data-remote tasks on \(s_{1}\). \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Server** & **Data-Local Task** & **Core** & **Initial Load** \\ \hline \multirow{2}{*}{\(s_{1}\)} & \multirow{2}{*}{\(t_{1}\)} & \(p_{11}\) & 0.75 \\  & & \(p_{12}\) & 0.5 \\ \hline \multirow{2}{*}{\(s_{2}\)} & \multirow{2}{*}{\(t_{1},t_{2},t_{3},t_{4}\)} & \(p_{21}\) & 0.25 \\  & & \(p_{22}\) & 2 \\ \hline \multirow{2}{*}{\(s_{3}\)} & \multirow{2}{*}{\(t_{3},t_{4},t_{5}\)} & \(p_{31}\) & 2.25 \\  & & \(p_{32}\) & 14 \\ \hline \multirow{2}{*}{\(s_{4}\)} & \multirow{2}{*}{\(t_{2},t_{5}\)} & \(p_{41}\) & 2.5 \\  & & \(p_{42}\) & 3.75 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: A scheduling instance (data-remote cost function \(g_{s}(n)=1+0.5n\)). Figure 2: Assignment strategies of three online scheduling algorithms (DL indicates “data-local” and DR indicates “data-remote”). (**a**) Hadoop’s assignment, \(\textit{makespan}=3.5\); (**b**) Delay scheduling’s assignment, \(\textit{makespan}=3.25\); (**c**) DynDLOn’s assignment, \(\textit{makespan}=3.25\). We use this heuristic for our online algorithm DynDLOn in Algorithm 1. Each core \(p\) is associated with two variables \(p.delay\) and \(p.wait\), which indicate the time to delay and the time \(p\) when waiting begins, respectively. When core \(p\) is free, DynDLOn first tries to assign a data-local task to \(p\). If not, DynDLOn compares \(p.wait\) and \(p.delay\), and assigns a data-remote task if \(p.wait\geq p.delay\). To set \(p.delay\), we consider two conditions. First, if server \(s\) does not contain a data-remote task, \(p.delay\) is set to a predefined value \(W\). In this case, DynDLOn rolls back to the original delay-scheduling algorithm. Second, if server \(s\) contains at least one data-remote task, we prefer starting a new data-remote task after a running data-remote task completes. Because a data-remote task's running time is \(g_{s}(r^{s})\), we set \(p.delay\) to \(\max\{g_{s}(r^{s}),W\}\), where \(r^{s}\) is the number of data-remote tasks on \(s\). ```
Input: Server \(s\), Core \(p\), Unscheduled Tasks \(T\), Data Placement \(DL^{srv}\) Output: Task assigned to \(p\) // \(p\) is an idle core on server \(s\). \(p.wait\) is the time \(p\) has waited. 1 foreach\(t\in T\)do
2 if\(s\) is in \(DL^{srv}(t)\)then
3\(p.wait\gets currentTime\) return\(t\) // \(r^{s}\) is the number of data-remote tasks on server \(s\). 4 if\(r^{s}==0\)then
5\(p.delay\gets W\)
6 else
7\(p.delay\leftarrow\max\{g_{s}(r^{s}),W\}\)
8\(wait\gets currentTime-p.wait\)
9 if\(p.wait\geq p.delay\)then
10\(p.wait\gets currentTime\) return\(randomtask(T)\) returnNULL
```  
**Algorithm 1**DynDLOn. The astute reader might feel that setting a longer duration of delay will decrease the system's utility, because the cores are idle while waiting. This is rare, though--it only happens when the system runs a few jobs. When there are more jobs, the idle core launches a task from another job to avoid decreasing the system's utility. Although we focus here on single-job systems, DynDLOn easily extends to multijob systems. In Section 6.2, we show DynDLOn's performance on multijob systems in real-world executions.