auxiliary task),and each task is local to C.Thus,the load is at most 3.The sink server is assigned three local sink tasks and the load is exactly 3.Therefore.all constraints are satisfied and A is feasible.This completes the proof of Lemma3.4.▣ The proof of the converse of Lemma 3.4 is more involved. The method is given a feasible assignment A in G=f(o),we Figure 3:The structure of the sink gadget. first construct a feasible assignment B in G such that B(t) P for all t ET-p1,p2,ps}.Then we remove the sink tasks and the sink server from further consideration and consider each variable task to the sink server P.We also connect the resulting graph G.After that,we partition G into two each literal task to a unique ring server R.To be more subgraphs,and construct a feasible assignment B'such that no tasks from one partition are remotely assigned to servers precise,if literal luv is the j-th occurrence of xi in o,connect the literal task to ring serverTi;if literal is in the other partition.This step involves a case analysis. Finally,a natural way of constructing the satisfying truth the j-th occurrence of r;in o,connect the literal task lu assignment for o follows to ring serverRFThese inter-gadget edges complete the graph G.Table 2 summarizes the parameters of G. LEMMA 3.5.Let A be a feasible task assignment.Then there erists a feasible task assignment B such that B(t)P Table 2:Parameters of the HMR-graph G for all t ET-{p1,p2,P3). clause server C literal task lu 3a PROOF.When A satisfies that A(t)≠P for all t∈T auxiliary task au ring server R 23w {p1,p2,p3},let B=A.Otherwise,assume there exists a ring taskr 26w variable task v Bw task t'such that A(t')=P and t'ET-{p1,p2,p3}.Since sink server P 1 sink task pj 3 the capacity of P is 3,there is at least one sink task,say pi, is not assigned to P.Let A(p1)=Q.Since p(p1,Q)does not hold,Q has only been assigned pi and L=3.Let LEMMA 3.2.For any E 3CNF,the graph f()is 2- B(p1)=P and B(t')=Q.Repeat the same process for all replica-bounded. tasks other than pi,p2,ps that are assigned to P in A.Then let B(t)=A(t)for the remaining tasks t E T.To see B is PRooF.We count the number of edges from each task feasible,,note that L≤La≤3 for all servers s∈S.口 node in f().Each clause task has 2 edges,each auxiliary task has 1 edge,each ring task has 2 edges,each variable Let G'be the subgraph induced by (T-{pi,p2,ps},S- task has 1 edge,and each sink task has 1 edge.Therefore. (P))=(T,S').We have the following lemma. f()is 2-replica-bounded. The following lemma is immediate. LEMMA 3.6.Let A be a feasible task assignment in G. Then there erists a feasible task assignment A'in G. LEMMA3.3.The mapping∫：3CNF一G is polynomial-- PROOF.Given A,Lemma 3.5 tells us that there exists time computable. another feasible assignment B in G such that B(t)P for LEMMA 3.4.If o is satisfiable,then G=f(o)is admis- all t E T.Let A'(t)=B(t)for all t E T'.Then A'is an sible. assignment in G since A'(t)ES-PI for all t E T.To see A'is feasible,note that L'L 3 for all servers PROOF.Let o be a satisfying truth assignment for o,and s∈S.☐ we construct a feasible assignment A in G=f().First of all,assign each sink task to the sink server,i.e.,let A(pi)= P for all ie[1,3].Then assign each auxiliary task au to the We further partition G'into two subgraphs Gc and GR. clause server Cu;i.e.,let A(au)=Cu for all u [1,a].If Gc is induced by nodes {Cu:uE [1,a]}ufau uE [1,a]}U a()=true,then assign ring tasks je[1,w to ring {luv u e [1,a],v E [1,3]}and GR is induced by nodes servers in Ti,variable tasksj[]to ring servers in {o:ieL,3,j∈[1,2}U{r:i∈[1，g,je1,2}U F.If a()=false,then assign ring tasksj1w u):i[1,B],j [1,w]).In other words,Gc consists of all clause gadgets while GR consists of all variable gadgets. to ring servers in Fi,variable tasks v:j[1,w]to ring If a task in one partition is remotely assigned to a server in servers in Ti.If literal luv =i and o(ti)=true,then assign the other partition,we call this task a cross-boundary task. task luv to its local ring server in Ti.If literal luv =i and Let ne be the number of cross-boundary tasks that are in o(ri)=false,then assign task l to its local ring server in Gc and assigned to servers in GR by A,n be the number of Fi.Otherwise,assign task lue to its local clause server Cu. cross-boundary tasks that are in GR and assigned to servers We then check this task assignment is feasible.Each ring in Gc by A.We have the following lemmas server is assigned either at most three local tasks (two ring tasks and one literal task),or one remote variable task.In LEMMA 3.7.Let A be a feasible assignment in G'such either case,the load does not exceed the capacity 3.The that n0 and n0.Then there erist a feasible assign- number of tasks assigned to each clause server Cu is exactly ment B in G'such that one of ne and nf equals nenA the number of false literals in Cu under o plus one (the and the other one equals 0.P 1 p 2 p 3 p Figure 3: The structure of the sink gadget. each variable task v (i) j to the sink server P. We also connect each literal task luv to a unique ring server R (i) j . To be more precise, if literal luv is the j-th occurrence of xi in φ, connect the literal task luv to ring server R (i) 2j−1 ∈ Ti; if literal luv is the j-th occurrence of ¬xi in φ, connect the literal task luv to ring server R (i) 2j ∈ Fi. These inter-gadget edges complete the graph G. Table 2 summarizes the parameters of G. Table 2: Parameters of the HMR-graph G clause server Cu α literal task luv 3α auxiliary task au α ring server R (i) j 2βω ring task r (i) j 2βω variable task v (i) j βω sink server P 1 sink task pj 3 Lemma 3.2. For any φ ∈ 3CNF, the graph f(φ) is 2- replica-bounded. Proof. We count the number of edges from each task node in f(φ). Each clause task has 2 edges, each auxiliary task has 1 edge, each ring task has 2 edges, each variable task has 1 edge, and each sink task has 1 edge. Therefore, f(φ) is 2-replica-bounded. The following lemma is immediate. Lemma 3.3. The mapping f : 3CNF → G is polynomial￾time computable. Lemma 3.4. If φ is satisfiable, then G = f(φ) is admis￾sible. Proof. Let σ be a satisfying truth assignment for φ, and we construct a feasible assignment A in G = f(φ). First of all, assign each sink task to the sink server, i.e., let A(pi) = P for all i ∈ [1, 3]. Then assign each auxiliary task au to the clause server Cu, i.e., let A(au) = Cu for all u ∈ [1, α]. If σ(xi) = true, then assign ring tasks r (i) j : j ∈ [1, 2ω] to ring servers in Ti, variable tasks v (i) j : j ∈ [1, ω] to ring servers in Fi. If σ(xi) = false, then assign ring tasks r (i) j : j ∈ [1, 2ω] to ring servers in Fi, variable tasks v (i) j : j ∈ [1, ω] to ring servers in Ti. If literal luv = xi and σ(xi) = true, then assign task luv to its local ring server in Ti. If literal luv = ¬xi and σ(xi) = false, then assign task luv to its local ring server in Fi. Otherwise, assign task luv to its local clause server Cu. We then check this task assignment is feasible. Each ring server is assigned either at most three local tasks (two ring tasks and one literal task), or one remote variable task. In either case, the load does not exceed the capacity 3. The number of tasks assigned to each clause server Cu is exactly the number of false literals in Cu under σ plus one (the auxiliary task), and each task is local to Cu. Thus, the load is at most 3. The sink server is assigned three local sink tasks and the load is exactly 3. Therefore, all constraints are satisfied and A is feasible. This completes the proof of Lemma 3.4. The proof of the converse of Lemma 3.4 is more involved. The method is given a feasible assignment A in G = f(φ), we first construct a feasible assignment B in G such that B(t) 6= P for all t ∈ T − {p1, p2, p3}. Then we remove the sink tasks and the sink server from further consideration and consider the resulting graph G 0 . After that, we partition G 0 into two subgraphs, and construct a feasible assignment B 0 such that no tasks from one partition are remotely assigned to servers in the other partition. This step involves a case analysis. Finally, a natural way of constructing the satisfying truth assignment for φ follows. Lemma 3.5. Let A be a feasible task assignment. Then there exists a feasible task assignment B such that B(t) 6= P for all t ∈ T − {p1, p2, p3}. Proof. When A satisfies that A(t) 6= P for all t ∈ T − {p1, p2, p3}, let B = A. Otherwise, assume there exists a task t 0 such that A(t 0 ) = P and t 0 ∈ T − {p1, p2, p3}. Since the capacity of P is 3, there is at least one sink task, say p1, is not assigned to P. Let A(p1) = Q. Since ρ(p1, Q) does not hold, Q has only been assigned p1 and L A Q = 3. Let B(p1) = P and B(t 0 ) = Q. Repeat the same process for all tasks other than p1, p2, p3 that are assigned to P in A. Then let B(t) = A(t) for the remaining tasks t ∈ T. To see B is feasible, note that L B s ≤ L A s ≤ 3 for all servers s ∈ S. Let G 0 be the subgraph induced by (T − {p1, p2, p3}, S − {P}) = (T 0 , S0 ). We have the following lemma. Lemma 3.6. Let A be a feasible task assignment in G. Then there exists a feasible task assignment A 0 in G 0 . Proof. Given A, Lemma 3.5 tells us that there exists another feasible assignment B in G such that B(t) 6= P for all t ∈ T 0 . Let A 0 (t) = B(t) for all t ∈ T 0 . Then A 0 is an assignment in G 0 since A 0 (t) ∈ S − {P} for all t ∈ T 0 . To see A 0 is feasible, note that L A0 s ≤ L B s ≤ 3 for all servers s ∈ S 0 . We further partition G 0 into two subgraphs GC and GR. GC is induced by nodes {Cu : u ∈ [1, α]}∪ {au : u ∈ [1, α]}∪ {luv : u ∈ [1, α], v ∈ [1, 3]} and GR is induced by nodes {R (i) j : i ∈ [1, β], j ∈ [1, 2ω]} ∪ {r (i) j : i ∈ [1, β], j ∈ [1, 2ω]} ∪ {v (i) j : i ∈ [1, β], j ∈ [1, ω]}. In other words, GC consists of all clause gadgets while GR consists of all variable gadgets. If a task in one partition is remotely assigned to a server in the other partition, we call this task a cross-boundary task. Let n A c be the number of cross-boundary tasks that are in GC and assigned to servers in GR by A, n A r be the number of cross-boundary tasks that are in GR and assigned to servers in GC by A. We have the following lemmas. Lemma 3.7. Let A be a feasible assignment in G 0 such that n A c > 0 and n A r > 0. Then there exist a feasible assign￾ment B in G 0 such that one of n B c and n B r equals |n A c − n A r | and the other one equals 0