## 2 Related Work  
The data-aware task scheduler is one of the most important parts in a distributed system. Over the past decade, many data-aware task-scheduling algorithms [23] were proposed to handle data locality [7; 8; 9; 10; 11; 12], heterogeneity [24; 25; 26], energy efficiency [27; 28], resource provision [29; 30], data emergency [31], workflow [32], and task preemption [33]. In this work, we focus on data-locality-aware task scheduling. The data locality problem is fundamental to data-intensive distributed computing. Early research works proposed data-locality-aware scheduling algorithms for Data Grid, an architecture that gives people the ability to access, modify, and transfer vast amounts of geographically distributed data. [PERSON] et al. [34] developed a simulator for Gfarm [35] (a data grid system), which used greedy scheduling algorithms to improve tasks' data localities. [PERSON] et al. [36] developed four scheduling algorithms: JobRandom, JobLeastLoaded, JobDataPresent, and JobLocal for Data Grids, where JobDataPresent was a data-locality-aware scheduling algorithm that scheduled jobs close to input data. [PERSON] et al. [37] implemented task diffusion on Falkon [38], a fast and lightweight task-execution framework. The data diffusion architecture's data-aware scheduler set the upper bound of the number of idle servers as a utility threshold. It skipped data-remote servers if the number of idle servers was below the utility threshold. However, the schedulers designed for Data Grids could not be applied readily to data-parallel frameworks, because the task execution models are different. Data Grid tasks are usually loosely coupled, so the scheduler's focus is on individual tasks, and scheduling algorithms are usually greedy and simple. In data-parallel frameworks, the tasks are relatively tightly coupled, because a job cannot finish until all of its subtasks are completed. Thus, the problem of how to develop a simple yet effective data-locality-aware scheduler has garnered the big data research community's attention. Hadoop [2] is a classic data-parallel framework based on MapReduce abstraction. Hadoop's default scheduling algorithm schedules jobs sequentially by a first-in, first-out policy. For the head-of-line job, the scheduler greedily searches for a data-local subtask for each idle server. If there is no data-local subtask, the scheduler randomly assigns a data-remote task. This task-scheduling algorithm is simple, so its data locality can be improved. [PERSON] et al. [7] proposed delay scheduling to improve fairness and data locality in a shared cluster. Delay scheduling implemented max-min fairness [39]: according to fairness, if the job to be scheduled could not launch a data-local task, it would wait until other jobs had launched a task. It was worthwhile to wait, because delay scheduling assumed that the server became idle quickly enough. However, when servers freed up slowly, delay scheduling did not work well. Quincy [8] took an approach similar to delay scheduling. Quincy was a centralized scheduler that used min-cost max-flow (MCMF) to solve the scheduling problem, and achieved better fairness. Firramament [9] improved Quincy in terms of scheduling latency. Data-locality-aware scheduling was also applied to graph computation systems. For example, [PERSON] et al. [21] compared the performance of two state-of-the-art big-data-analytic architectures (Kappa and Lambda) when deployed onto a public-cloud PaaS (Platform as a Service) running social network analysis applications. Our work is orthogonal to this work. Since Kappa and Lambda are Spark-based systems, our work can be applied to the systems to accelerate distributed social network analysis [20]. Some data-locality-aware approaches were designed to optimize throughput and handle data skew. To optimize throughput, [PERSON] et al. [10] designed a novel queueing architecture for data-parallel task scheduling by using a \"join the shortest queue\" (JSQ) policy and a MaxWeight policy. [PERSON] et al.