Social Locality in Data Storage - Data Storage for Social Networks: A Socially Aware Approach - page 24

2. If j is not primarily assigned to s (i.e., p js D 0): if there exists a neighbor i
primarily assigned to s (i.e., e ij >0, p is D 1), then x js D 1;otherwise,x js D 0.
In any case, we can formulate x js as

!

N

Y

x js D .1 p js / 1 .1 d p is e ij e /

i D 1

and so there is no optimization involved.

2.4.2.2 Replication with Imperfect Social Locality

Imperfect social locality is the case for systems with limited storage budget for
replication. Also, although users are not equally active in the network, they should
deserve the same degree of data availability so that everyone has an equal chance to
successfully access data under any failure condition. Therefore, a useful constraint
is to the same number, K, of replicas for each user, in addition to their primary

copy; i.e.,

X

M

x is D K for 1 i

N:

(2.22)

s D 1

With this constraint, the total write load and storage load can be simplified as

! D .K C 1/

X

N

X

M

X

N

write

L D w i 1 C x is w i (2.23)

i D 1 s D 1 i D 1

N M

X X

store

L D N C x is D N.K C 1/ (2.24)

i D 1 s D 1

Since these loads are fixed regardless of the replication scheme, we focus on
minimizing the total read load and balancing read load, write load, and storage load.
The problem, therefore, is modeled as follows:

Problem 2.2 (Replication). Find the best binary matrix X

L

store T read read write

minimize
X

;G ;G ;G

1/ x is 1 p is for 1 i

N; 1 s M

subject to

X

M

2/ x is D K for 1 i N

s D 1