l≤i≤n,and thus L4=woc.Now we add one edge The virtual load of server s under B from a is VB.o= between task tn and server s1.We run Algorithm 1 on this ∑teae=sv(化，3).The marimum virtual load under B from new placement graph G'to get assignment A'.It might a is vB.a maxses V.a. assign task tn to server s1 in the first step.Following that it assigns ti to si for 2 <i<n-1,and it finally assigns Thus,v assumes pessimistically that tasks not assigned by ti to sn.Since ti is remote to sn,this gives L4'=wrem B will eventually become remote,and each remote task will Therefore L4'>LA.▣ eventully have cost wfem.When a is clear from context,we omit a and write v(t,B),Vs and Va,respectively.Note Theorem 4.1 indicates that increasing the number of data that v(t,a)=w(t,a)as in Definition 7. block replicas is not always beneficial for Algorithm 1.In the Algorithm 2 works iteratively to produce a sequence of remaining part of this section,we show that the assignments assignments and then outputs the best one,i.e.,the one of computed by Algorithm 1 might deviate from the optimum least maximum server load.The iteration is controlled by an by a multiplicative factor.In the following,let O be an integer variable r which is initialized to 1 and incremented assignment that minimizes Lo on each iteration.Each iteration consists of two phases, THEOREM 4.2.Let A be an assignment computed by Al- mar-cover and bal-assign: gorithm1.Then LA≤(urem/moe)·L9 Mar-cover:Given as input a placement graph Go,an PROOF.On the one hand,pigeonhole principle says there integer value T,and a partial assignment a,max-cover is a server assigned at least m/n tasks.Since the cost of returns a partial assignment a'of a subset T of tasks. each task is at least wloc,the load of this server is at least such that a'assigns no server more than r tasks,every [m/n].woc.Thus,LO≥「m/ml·oec.On the other hand, task in T is local in a',and T is maximized over Algorithm 1 runs in a round robin fashion where one task is all such assignments.Thus,a'makes as many tasks assigned at a time.Therefore,the number of tasks assigned local as is possible without assigning more than r tasks to each server is at most m/n.Since the cost of each task to any one server.The name "max-cover"follows the is at most wrem,the load of a server is at most m/n Wrem. intuition that we are actually trying to "cover"as many Thus,LA≤[m/nl,wre, Combining the two,we have tasks as possible by their local servers,subject to the LA≤(wrem/hoc)·LO.▣ constraint that no server is assigned more than r tasks THEOREM 4.3.Let T and S be such that m<n(n-2) Bal-assign:Given as input a set of tasks T,a set of There erist a placement p and an assignment A such that A servers S,a partial assignment a computed by max- e3 oupulo时Algorithm1,L≥lm/m:1 cover,and a cost function w,bal-assign uses a simple =「m/n·w1oe. greedy algorithm to extend a to a complete assignment PROOF.We prove the theorem by constructing a place- B by repeatedly choosing a server with minimal virtual ment graph Ge.Partition the set T of tasks into n disjoint load and assigning some unassigned task to it.This subsets T::1≤i≤n,such that「m/nl≥T≥lT引≥ continues until all tasks are assigned.It thus generates Lm/n]for all1≤i≤j≤n.Now in the placement graph a sequence of partial assignments a=ao Ca1C...C ofuthat品h ,for all1≤i≤_n u=B,where u =u.Every task t assigned in bal- assign contributes v(t,B)<wfem to the virtual load then connect each task in T to a different server in the sub- of the server that it is assigned to.At the end,wrem set S={s1,s2,...,sn-1}.Since m n(n-2),we have wem,and equality holds only whenrr+u 「m/nl≤m/n+1≤n-l,which guarantees S≥lTnl This completes the placement graph Ge.Now run Algo- The astute reader might feel that it is intellectually attrac- rithm 1 on Ge.There is a possible output A where tasks in tive to use real server load as the criterion to choose servers Tn are assigned to servers in S'.In that case,all tasks that in bal-assign because it embeds more accurate information. are local to server sn are assigned elsewhere,and thus sn is We do not know if this change ever results in a better as- assigned remote tasks.Since s is assigned at least [m/n] signment.We do know that it may require more compu- tasks,this gives L4≥Lm/n·wrem:□ tation.Whenever a local task is assigned,r+u decreases by 1,so the remote cost wrem(r+u)may also decrease.If When n m.the lower bound in Theorem 4.3 matches the it does,the loads of all servers that have been assigned re- upper bound in Theorem 4.2. mote tasks must be recomputed.In the current version of 5.A FLOW-BASED ALGORITHM the algorithm,we do not need to update virtual load when a local task is assigned because the virtual cost of remote Theorem 3.1 shows that the problem of computing an op- tasks never changes in the course of bal-assign. timal task assignment for the HTA problem is NP-complete. Nevertheless,it is feasible to find task assignments whose 5.1 Algorithm Description load is at most an additive constant greater than the opti- We describe Algorithm 2 in greater detail here. mal load.We present such an algorithm in this section. For two partial assignments a and B such that BD o,we 5.1.1 Max-cover define a new notation called virtual load from a below. Max-cover (line 6 of Algorithm 2)augments the partial Definition 12.For any task t and partial assignment B assignment a"computed by the previous iteration to pro- duce a".(We define ao to be the empty partial assignment.) that extends o,let Thus,a2a"-1,and a"maximizes the total number of lo- v(t,)= Wloc if t is local in B, cal tasks assigned subject to the constraint that no server is otherwise. assigned more than r tasks in all.1 ≤ i ≤ n, and thus L A = wloc. Now we add one edge between task tn and server s1. We run Algorithm 1 on this new placement graph G 0 to get assignment A 0 . It might assign task tn to server s1 in the first step. Following that, it assigns ti to si for 2 ≤ i ≤ n − 1, and it finally assigns t1 to sn. Since t1 is remote to sn, this gives L A0 = wrem. Therefore L A0 > LA. Theorem 4.1 indicates that increasing the number of data block replicas is not always beneficial for Algorithm 1. In the remaining part of this section, we show that the assignments computed by Algorithm 1 might deviate from the optimum by a multiplicative factor. In the following, let O be an assignment that minimizes L O. Theorem 4.2. Let A be an assignment computed by Al￾gorithm 1. Then L A ≤ (wrem/wloc) · L O. Proof. On the one hand, pigeonhole principle says there is a server assigned at least dm/ne tasks. Since the cost of each task is at least wloc, the load of this server is at least dm/ne · wloc. Thus, L O ≥ dm/ne · wloc. On the other hand, Algorithm 1 runs in a round robin fashion where one task is assigned at a time. Therefore, the number of tasks assigned to each server is at most dm/ne. Since the cost of each task is at most wrem, the load of a server is at most dm/ne·wrem. Thus, L A ≤ dm/ne · wrem. Combining the two, we have L A ≤ (wrem/wloc) · L O. Theorem 4.3. Let T and S be such that m ≤ n(n − 2). There exist a placement ρ and an assignment A such that A is a possible output of Algorithm 1, L A ≥ bm/nc · wrem, and L O = dm/ne · wloc. Proof. We prove the theorem by constructing a place￾ment graph Gρ. Partition the set T of tasks into n disjoint subsets Ti : 1 ≤ i ≤ n, such that dm/ne ≥ |Ti| ≥ |Tj | ≥ bm/nc for all 1 ≤ i ≤ j ≤ n. Now in the placement graph Gρ, connect tasks in Ti to server si, for all 1 ≤ i ≤ n. These set of edges guarantee that L O = dm/ne · wloc. We then connect each task in Tn to a different server in the sub￾set S 0 = {s1, s2, · · · , sn−1}. Since m ≤ n(n − 2), we have dm/ne ≤ m/n + 1 ≤ n − 1, which guarantees |S 0 | ≥ |Tn|. This completes the placement graph Gρ. Now run Algo￾rithm 1 on Gρ. There is a possible output A where tasks in Tn are assigned to servers in S 0 . In that case, all tasks that are local to server sn are assigned elsewhere, and thus sn is assigned remote tasks. Since sn is assigned at least bm/nc tasks, this gives L A ≥ bm/nc · wrem. When n | m, the lower bound in Theorem 4.3 matches the upper bound in Theorem 4.2. 5. A FLOW-BASED ALGORITHM Theorem 3.1 shows that the problem of computing an op￾timal task assignment for the HTA problem is N P-complete. Nevertheless, it is feasible to find task assignments whose load is at most an additive constant greater than the opti￾mal load. We present such an algorithm in this section. For two partial assignments α and β such that β ⊇ α, we define a new notation called virtual load from α below. Definition 12. For any task t and partial assignment β that extends α, let v α (t, β) =  wloc if t is local in β, w α rem otherwise. The virtual load of server s under β from α is V β,α P s = t:β(t)=s v α (t, β). The maximum virtual load under β from α is V β,α = maxs∈S V β,α s . Thus, v assumes pessimistically that tasks not assigned by β will eventually become remote, and each remote task will eventully have cost w α rem. When α is clear from context, we omit α and write v(t, β), V β s and V β , respectively. Note that v α (t, α) = w(t, α) as in Definition 7. Algorithm 2 works iteratively to produce a sequence of assignments and then outputs the best one, i.e., the one of least maximum server load. The iteration is controlled by an integer variable τ which is initialized to 1 and incremented on each iteration. Each iteration consists of two phases, max-cover and bal-assign: • Max-cover : Given as input a placement graph Gρ, an integer value τ , and a partial assignment α, max-cover returns a partial assignment α 0 of a subset T 0 of tasks, such that α 0 assigns no server more than τ tasks, every task in T 0 is local in α 0 , and |T 0 | is maximized over all such assignments. Thus, α 0 makes as many tasks local as is possible without assigning more than τ tasks to any one server. The name “max-cover” follows the intuition that we are actually trying to “cover” as many tasks as possible by their local servers, subject to the constraint that no server is assigned more than τ tasks. • Bal-assign: Given as input a set of tasks T, a set of servers S, a partial assignment α computed by max￾cover, and a cost function w, bal-assign uses a simple greedy algorithm to extend α to a complete assignment B by repeatedly choosing a server with minimal virtual load and assigning some unassigned task to it. This continues until all tasks are assigned. It thus generates a sequence of partial assignments α = α0 ⊆ α1 ⊆ · · · ⊆ αu = B, where u = u α . Every task t assigned in bal￾assign contributes v α (t, B) ≤ w α rem to the virtual load of the server that it is assigned to. At the end, w B rem ≤ w α rem, and equality holds only when r B = r α + u α . The astute reader might feel that it is intellectually attrac￾tive to use real server load as the criterion to choose servers in bal-assign because it embeds more accurate information. We do not know if this change ever results in a better as￾signment. We do know that it may require more compu￾tation. Whenever a local task is assigned, r + u decreases by 1, so the remote cost wrem(r + u) may also decrease. If it does, the loads of all servers that have been assigned re￾mote tasks must be recomputed. In the current version of the algorithm, we do not need to update virtual load when a local task is assigned because the virtual cost of remote tasks never changes in the course of bal-assign. 5.1 Algorithm Description We describe Algorithm 2 in greater detail here. 5.1.1 Max-cover Max-cover (line 6 of Algorithm 2) augments the partial assignment α τ−1 computed by the previous iteration to pro￾duce α τ . (We define α 0 to be the empty partial assignment.) Thus, α τ ⊇ α τ−1 , and α τ maximizes the total number of lo￾cal tasks assigned subject to the constraint that no server is assigned more than τ tasks in all