Our notion of an MR-system is very general and admits The definition of remote cost under a partial assignment B arbitrary cost functions.To usefully model Hadoop as an is pessimistic.It assumes that tasks not assigned by B will MR-system,we need a realistic but simplified cost model. eventually become remote,and each remote task will even- In Hadoop,the cost of a map task depends frequently on tually have costrem(+).This definition agrees with the location of its data.If the data is on the server's local the definition of remote cost under a complete assignment A. disk,then the cost (execution time)is considerably lower because u4 =0 and thus wrem =Wrem(rA+u4)=Wrem(rA) than if the data is located remotely and must be fetched Since p is encoded by mn bits,wloe is encoded by one across the network before being processed. rational number,and wrem()is encoded by m+1 ratio- We make several simplifying assumptions.We assume nal numbers,the Hadoop cost function w(p,wloe,Wrem())is that all tasks and all servers are identical,so that for any encoded by mn bits plus m+2 rational numbers. particular assignment of tasks to servers,all tasks whose data is locally available take the same amount of time wloe, Definition 8.A Hadoop MR-system (HMR-system)is the and all tasks whose data is remote take the same amount MR-system (T,S,w),where w is the Hadoop cost function of time wrem.However,we do not assume that wrem is con- with parameters p,wloc,and wrem().A HMR-system is stant over all assignments.Rather,we let it grow with the defined by (T,S,p,whoe,Wrem()). total number of tasks whose data is remote.This reflects the increased data fetch time due to overall network con- gestion.Thus,wrem(r)is the cost of each remote task in Problem 1 Hadoop Task Assignment Problem (HTA) every assignment with exactly r remote tasks.We assume that wrem(r)>wioe for all r and that wrem(r)is (weakly) 1.Instance:An HMR-system (T,S,p,whoc,Wrem()). monotone increasing in r. We formalize these concepts below.In each of the follow- 2.Objective:Find an assignment A that minimizes L4. ing,(T,S)is an MR-schema. Definition 3.A data placement is a relation p C T x S Sometimes the cost of running a task on a server only such that for every task t E T,there exists at least one server depends on the placement relation and its data locality,but sES such that p(t,s)holds. not on the assignment of other tasks. The placement relation describes where the input data blocks are placed.If p(t,s)holds,then server s locally stores Definition 9.A Hadoop cost function w is called uniform if wrem(r)=c for some constant c and all r E N.A a replica of the data block that task t needs. uniform HMR-system (UHMR-system)is an HMR-system Definition 4.We represent the placement relation p by an (T,S,p,wloe,Wrem()),where w is uniform. unweighted bipartite graph,called the placement graph.In the placement graph Ge =((T,S),E),T consists of m task nodes and S consists of n server nodes.There is an edge Problem 2 Uniform Hadoop Task Assignment Problem (t,s)E iff p(t,s)holds. (UHTA) Definition 5.A partial assignment a is a partial function 1.Instance:A UHMR-system (T,S,p,wioe,Wrem()) from T to S.We regard a partial assignment as a set of 2.Objective:Find an assignment A that minimizes L4. ordered pairs with pairwise distinct first elements,so for partial assignments B and o,B a means B ertends a.If s ES,the restriction of a to s is the partial assignment als=an(T x {s}).Thus,als agrees with a for those tasks The number of replicas of each data block may be that a assigns to s,but all other tasks are unassigned in l. bounded,often by a small number such as 2 or 3. Definition 6.Let p be a data placement and 3 be a partial Definition 10.Call a placement graph G=((T,S),E)j- assignment.A task t E T is local in B if B(t)is defined and replica-bounded if the degree of t is at most j for all t E T. p(t,B(t)).A task tT is remote in a if B(t)is defined A j-replica-bounded-UHMR-system (j-UHMR-system)is a and p(t,B(t)).Otherwise t is unassigned in B.Let e UHMR-system(T,S,p,wloc,Wrem()),where Ge is j-replica- r3 and u3 be the number of local tasks,remote tasks,and bounded. unassigned tasks in B,respectively.For any s E S,let es be the number of local tasks assigned to s by B.Let k= maxs∈sg. Problem 3 j-Uniform Hadoop Task Assignment Problem (j-UHTA) Definition 7.Let p be a data placement,B be a partial assignment,hoe∈Q+,and Wrem:N一Q+such that wioe≤ 1.Instance:A j-UHMR-system (T,S,p,Wioe,Wrem()). wrem(O）≤rem(1)≤wrem(②).…Let wrem=urem(r3 2.Objective:Find an assignment A that minimizes L4. u).The Hadoop cost function with parameters p,wloe, and wrem()is the function w defined by w(t,B)= 了oe if t is local in B, 3.HARDNESS OF TASK ASSIGNMENT wrem otherwise. In this section,we analyze the hardness of the various We call p the placement of w,and wloe and wrem()the local HTA optimization problems by showing the corresponding and remote costs of w,respectively.Let K=k.woc. decision problems to be AP-complete.Our notion of an MR-system is very general and admits arbitrary cost functions. To usefully model Hadoop as an MR-system, we need a realistic but simplified cost model. In Hadoop, the cost of a map task depends frequently on the location of its data. If the data is on the server’s local disk, then the cost (execution time) is considerably lower than if the data is located remotely and must be fetched across the network before being processed. We make several simplifying assumptions. We assume that all tasks and all servers are identical, so that for any particular assignment of tasks to servers, all tasks whose data is locally available take the same amount of time wloc, and all tasks whose data is remote take the same amount of time wrem. However, we do not assume that wrem is con￾stant over all assignments. Rather, we let it grow with the total number of tasks whose data is remote. This reflects the increased data fetch time due to overall network con￾gestion. Thus, wrem(r) is the cost of each remote task in every assignment with exactly r remote tasks. We assume that wrem(r) ≥ wloc for all r and that wrem(r) is (weakly) monotone increasing in r. We formalize these concepts below. In each of the follow￾ing, (T, S) is an MR-schema. Definition 3. A data placement is a relation ρ ⊆ T × S such that for every task t ∈ T, there exists at least one server s ∈ S such that ρ(t, s) holds. The placement relation describes where the input data blocks are placed. If ρ(t, s) holds, then server s locally stores a replica of the data block that task t needs. Definition 4. We represent the placement relation ρ by an unweighted bipartite graph, called the placement graph. In the placement graph Gρ = ((T, S), E), T consists of m task nodes and S consists of n server nodes. There is an edge (t, s) ∈ E iff ρ(t, s) holds. Definition 5. A partial assignment α is a partial function from T to S. We regard a partial assignment as a set of ordered pairs with pairwise distinct first elements, so for partial assignments β and α, β ⊇ α means β extends α. If s ∈ S, the restriction of α to s is the partial assignment α|s = α∩(T × {s}). Thus, α|s agrees with α for those tasks that α assigns to s, but all other tasks are unassigned in α|s. Definition 6. Let ρ be a data placement and β be a partial assignment. A task t ∈ T is local in β if β(t) is defined and ρ(t, β(t)). A task t ∈ T is remote in α if β(t) is defined and ¬ρ(t, β(t)). Otherwise t is unassigned in β. Let ` β , r β and u β be the number of local tasks, remote tasks, and unassigned tasks in β, respectively. For any s ∈ S, let ` β s be the number of local tasks assigned to s by β. Let k β = maxs∈S ` β s . Definition 7. Let ρ be a data placement, β be a partial assignment, wloc ∈ Q +, and wrem : N → Q + such that wloc ≤ wrem(0) ≤ wrem(1) ≤ wrem(2). . .. Let w β rem = wrem(r β + u β ). The Hadoop cost function with parameters ρ, wloc, and wrem(·) is the function w defined by w(t, β) =  wloc if t is local in β, w β rem otherwise. We call ρ the placement of w, and wloc and wrem(·) the local and remote costs of w, respectively. Let Kβ = k β · wloc. The definition of remote cost under a partial assignment β is pessimistic. It assumes that tasks not assigned by β will eventually become remote, and each remote task will even￾tually have cost wrem(r β + u β ). This definition agrees with the definition of remote cost under a complete assignment A, because u A = 0 and thus w A rem = wrem(r A+u A) = wrem(r A). Since ρ is encoded by mn bits, wloc is encoded by one rational number, and wrem(·) is encoded by m + 1 ratio￾nal numbers, the Hadoop cost function w(ρ, wloc, wrem(·)) is encoded by mn bits plus m + 2 rational numbers. Definition 8. A Hadoop MR-system (HMR-system) is the MR-system (T, S, w), where w is the Hadoop cost function with parameters ρ, wloc, and wrem(·). A HMR-system is defined by (T, S, ρ, wloc, wrem(·)). Problem 1 Hadoop Task Assignment Problem (HTA) 1. Instance: An HMR-system (T, S, ρ, wloc, wrem(·)). 2. Objective: Find an assignment A that minimizes L A. Sometimes the cost of running a task on a server only depends on the placement relation and its data locality, but not on the assignment of other tasks. Definition 9. A Hadoop cost function w is called uniform if wrem(r) = c for some constant c and all r ∈ N. A uniform HMR-system (UHMR-system) is an HMR-system (T, S, ρ, wloc, wrem(·)), where w is uniform. Problem 2 Uniform Hadoop Task Assignment Problem (UHTA) 1. Instance: A UHMR-system (T, S, ρ, wloc, wrem(·)). 2. Objective: Find an assignment A that minimizes L A. The number of replicas of each data block may be bounded, often by a small number such as 2 or 3. Definition 10. Call a placement graph G = ((T, S), E) j￾replica-bounded if the degree of t is at most j for all t ∈ T. A j-replica-bounded-UHMR-system (j-UHMR-system) is a UHMR-system (T, S, ρ, wloc, wrem(·)), where Gρ is j-replica￾bounded. Problem 3 j-Uniform Hadoop Task Assignment Problem (j-UHTA) 1. Instance: A j-UHMR-system (T, S, ρ, wloc, wrem(·)). 2. Objective: Find an assignment A that minimizes L A. 3. HARDNESS OF TASK ASSIGNMENT In this section, we analyze the hardness of the various HTA optimization problems by showing the corresponding decision problems to be N P-complete