Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Task-Cloning Algorithms in a MapReduce Cluster with Competitive
  Performance Bounds   Job scheduling for a MapReduce cluster has been an active research topic in
recent years. However, measurement traces from real-world production
environment show that the duration of tasks within a job vary widely. The
overall elapsed time of a job, i.e. the so-called flowtime, is often dictated
by one or few slowly-running tasks within a job, generally referred as the
"stragglers". The cause of stragglers include tasks running on
partially/intermittently failing machines or the existence of some localized
resource bottleneck(s) within a MapReduce cluster. To tackle this online job
scheduling challenge, we adopt the task cloning approach and design the
corresponding scheduling algorithms which aim at minimizing the weighted sum of
job flowtimes in a MapReduce cluster based on the Shortest Remaining Processing
Time scheduler (SRPT). To be more specific, we first design a 2-competitive
offline algorithm when the variance of task-duration is negligible. We then
extend this offline algorithm to yield the so-called SRPTMS+C algorithm for the
online case and show that SRPTMS+C is $(1+\epsilon)-speed$
$o(\frac{1}{\epsilon^2})-competitive$ in reducing the weighted sum of job
flowtimes within a cluster. Both of the algorithms explicitly consider the
precedence constraints between the two phases within the MapReduce framework.
We also demonstrate via trace-driven simulations that SRPTMS+C can
significantly reduce the weighted/unweighted sum of job flowtimes by cutting
down the elapsed time of small jobs substantially. In particular, SRPTMS+C
beats the Microsoft Mantri scheme by nearly 25% according to this metric.

8
The categories of this paper are: hep-ex
0
The categories of this paper are: hep-ph
23
The categories of this paper are: solv-int
9
The categories of this paper are: nlin
14
The categories of this paper are: math-ph
19
The categories of this paper are: eess
2
The categories of this paper are: math
5
The categories of this paper are: gr-qc
12
The categories of this paper are: nucl-th
21
The categories of this paper are: adap-org
15
The categories of this paper are: nucl-ex
11
The categories of this paper are: hep-lat
34
The categories of this paper are: chem-ph
37
The categories of this paper are: supr-con
22
The categories of this paper are: chao-dyn
17
The categories of this paper are: q-fin