3.1 Task Assignment Decision Problems tasks lu1,lu2,lu3 and an auriliary task au.There is an edge between each of these tasks and the clause server.Since o Definition 11.Given a server capacity k,a task assign- contains a clauses,G contains a clause gadgets.Thus,G ment A is k-feasible if L4 k.An HMR-system is k- contains a clause servers,3o literal tasks and a auxiliary admissible if there exists a k-feasible task assignment tasks.Figure 1 describes the structure of the u-th clause gadget.We use circles and boxes to represent tasks and The decision problem corresponding to a class of HMR- servers,respectively systems and capacity k asks whether a given HMR-system in the class is k-admissible.Thus,the k-HTA problem asks about arbitrary HMR-systems,the k-UHTA problem asks about arbitrary UHMR-systems,and the k-j-UHTA prob- lem (which we write (j,k)-UHTA)asks about arbitrary j- UHMR-systems. 3.2 NP-completeness of(2,3)-UHTA The (2,3)-UHTA problem is a very restricted subclass of the general k-admissibility problem for HMR-systems.In this section,we restrict even further by taking wnoe =1 and wrem =3.This problem represents a simple scenario where the cost function assumes only the two possible values 1 and 3.each data block has at most 2 replicas,and each Figure 1:The structure of the u-th clause gadget. server has capacity 3.Despite its obvious simplicity,we show that (2,3)-UHTA is AP-complete.It follows that all of the The second type of gadget is called a variable gadget.Each less restritive decision problems are also NP-complete,and variable gadget contains 2w ring servers placed around a the correponding optimization problems do not have feasible circle.Let R denote the server at positionj1,w in solutions unless p=Ap ring i.Define the set Ti to be the servers in odd-numbered positions.Similarly,define the set Fi to be the servers in THEOREM 3.1.(2,3)-UHTA with costs wloe 1 and even-numbered positions.Between each pair of ring servers Wrem =3 is NP-complete. Rand we place a ring taskconected to its two The proof method is to construct a polynomial-time re- neighboring servers.To complete the circle,is connected duction from 3SAT to (2,3)-UHTA.Let g be the set of to R and R).There are also w variable tasks v:jE all 2-replica-bounded placement graphs.Given GeE g, [1,w]in ring i,but they do not connect to any ring server. we define the HMR-system MG =(T,S,p,wloe,wrem()), Since contains B variables,G contains B variable gadgets. where wioe =1 and wrem(r)=3 for all r.We say that Thus,G contains 2Bw ring servers,23w ring tasks and Bw G is 3-admissible if MG is 3-admissible.We construct a variable tasks.Figure 2 describes the structure of the i-th polynomial-time computable mapping f:3CNF-G,and variable gadget. show that a 3CNF formula o is satisfiable iff f(o)is 3- admissible.Ve shorten“3-admissible”to“admissible”in the following discussion. We first describe the construction of f.Let =CIA C2...AC be a 3CNF formula,where each Cu=(Vlu2V 2) lus)is a clause and each luv is a literal.Let 1,..,ra be the variables that appear in Therefore,contains exactly 3a instances of literals,each of which is either ri or i,where i [1,B].3 Let w be the maximum number of occurrences of any literal in o.Table 1 summarizes the parameters of o. Table 1:Parameters of the 3CNF clauses (Cu)a variables (vi)B literals (lu)3a max-occur of any literalw For example,in (1 V x2 V E3)A (1 V-4 V Is)A (T1 Vx4 V-Z6),we have a=3,B=6,and w=2 since Ti occurs twice. Given o,we construct the corresponding placement graph Figure 2:The structure of the i-th variable gadget. G which comprises several disjoint copies of the three types of gadget described below,connected together with addi- The third type of gadget is called a sink gadget.The tional edges. sink gadget contains a sink server P and three sink tasks The first type of gadget is called a clause gadget.Each pi,p2,P3.Each sink task is connected to the sink server. clause gadget u contains a clause server Cu,three literal G only contains one sink gadget.Figure 3 describes the 3The notation [a,b]in our discussion represents the set of structure of the sink gadget. integers fa,a+1,...,6-1,b. There are also some inter-gadget edges in G.We connect3.1 Task Assignment Decision Problems Definition 11. Given a server capacity k, a task assignment A is k-feasible if L A ≤ k. An HMR-system is kadmissible if there exists a k-feasible task assignment. The decision problem corresponding to a class of HMRsystems and capacity k asks whether a given HMR-system in the class is k-admissible. Thus, the k-HTA problem asks about arbitrary HMR-systems, the k-UHTA problem asks about arbitrary UHMR-systems, and the k-j-UHTA problem (which we write (j, k)-UHTA) asks about arbitrary jUHMR-systems. 3.2 N P-completeness of (2,3)-UHTA The (2,3)-UHTA problem is a very restricted subclass of the general k-admissibility problem for HMR-systems. In this section, we restrict even further by taking wloc = 1 and wrem = 3. This problem represents a simple scenario where the cost function assumes only the two possible values 1 and 3, each data block has at most 2 replicas, and each server has capacity 3. Despite its obvious simplicity, we show that (2,3)-UHTA is N P-complete. It follows that all of the less restritive decision problems are also N P-complete, and the correponding optimization problems do not have feasible solutions unless P = N P. Theorem 3.1. (2, 3)-UHTA with costs wloc = 1 and wrem = 3 is N P-complete. The proof method is to construct a polynomial-time reduction from 3SAT to (2,3)-UHTA. Let G be the set of all 2-replica-bounded placement graphs. Given Gρ ∈ G, we define the HMR-system MG = (T, S, ρ, wloc, wrem(·)), where wloc = 1 and wrem(r) = 3 for all r. We say that G is 3-admissible if MG is 3-admissible. We construct a polynomial-time computable mapping f : 3CNF → G, and show that a 3CNF formula φ is satisfiable iff f(φ) is 3- admissible. We shorten “3-admissible” to “admissible” in the following discussion. We first describe the construction of f. Let φ = C1 ∧ C2 · · ·∧Cα be a 3CNF formula, where each Cu = (lu1∨lu2∨ lu3) is a clause and each luv is a literal. Let x1, · · · , xβ be the variables that appear in φ. Therefore, φ contains exactly 3α instances of literals, each of which is either xi or ¬xi, where i ∈ [1, β].3 Let ω be the maximum number of occurrences of any literal in φ. Table 1 summarizes the parameters of φ. Table 1: Parameters of the 3CNF φ clauses (Cu) α variables (vi) β literals (luv) 3α max-occur of any literal ω For example, in φ = (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ ¬x4 ∨ x5) ∧ (¬x1 ∨ x4 ∨ ¬x6), we have α = 3, β = 6, and ω = 2 since x1 occurs twice. Given φ, we construct the corresponding placement graph G which comprises several disjoint copies of the three types of gadget described below, connected together with additional edges. The first type of gadget is called a clause gadget. Each clause gadget u contains a clause server Cu, three literal 3The notation [a,b] in our discussion represents the set of integers {a, a + 1, · · · , b − 1, b}. tasks lu1, lu2, lu3 and an auxiliary task au. There is an edge between each of these tasks and the clause server. Since φ contains α clauses, G contains α clause gadgets. Thus, G contains α clause servers, 3α literal tasks and α auxiliary tasks. Figure 1 describes the structure of the u-th clause gadget. We use circles and boxes to represent tasks and servers, respectively. Cu u1 lu2 lu3 l u a Figure 1: The structure of the u-th clause gadget. The second type of gadget is called a variable gadget. Each variable gadget contains 2ω ring servers placed around a circle. Let R (i) j denote the server at position j ∈ [1, 2ω] in ring i. Define the set Ti to be the servers in odd-numbered positions. Similarly, define the set Fi to be the servers in even-numbered positions. Between each pair of ring servers R (i) j and R (i) j+1, we place a ring task r (i) j connected to its two neighboring servers. To complete the circle, r (i) 2ω is connected to R (i) 2ω and R (i) 1 . There are also ω variable tasks v (i) j : j ∈ [1, ω] in ring i, but they do not connect to any ring server. Since φ contains β variables, G contains β variable gadgets. Thus, G contains 2βω ring servers, 2βω ring tasks and βω variable tasks. Figure 2 describes the structure of the i-th variable gadget. ( ) 1 i R ( ) 2 i r ( ) 2 i R ( ) 3 i R ( ) 2 i R ( ) 1 i r ( ) 2 i r ( ) 1 i v ( ) 2 i v (i) v Ti Fi Ti Ti Ti Fi Fi Fi Figure 2: The structure of the i-th variable gadget. The third type of gadget is called a sink gadget. The sink gadget contains a sink server P and three sink tasks p1, p2, p3. Each sink task is connected to the sink server. G only contains one sink gadget. Figure 3 describes the structure of the sink gadget. There are also some inter-gadget edges in G. We connect