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

2.4.2 The Replication Problem

In this problem, we are given a partition which already assigns users to their
corresponding servers (i.e., matrix P is known) and required to find the best
replication assignment (X ). As aforementioned in Sect. 2.1 , we may have different
objectives depending whether the system can afford perfect social locality or
imperfect social locality.

2.4.2.1 Replication with Perfect Social Locality

With perfect social locality, every user must have its neighbor users primarily stored
or replicated on its primary server. Read requests, therefore, do not have to go cross-
server. Given a server s, its read load is incurred only due to read requests initiated
by its primarily assigned users,

X

N

read
s

l D r i p is :

i D 1

Hence,

M N

X X

read

L D r i p is

s D 1 i D 1

X

N

X

M

D

r i p is

i D 1 s D 1

X

N

D r i :

i D 1

Individual read loads and the total read load are independent of the replication
scheme. It turns out that there is only one replication scheme that satisfies the
requirement for perfect social locality. This requirement can be represented by the
following constraint

e ij p is .1 p js /.1 x js / D 0 for 1 i; j N; 1 s M

i.e., given a user i who is primarily located at server s (i.e., p is D 1), for each

neighbor j (i.e., e ij >0), we must have either j is primarily assigned to s (i.e.,

p js D 1)orareplicaofj is at s (i.e., x js D 1).
Consequently, given a server s and a user j , there are two cases:

1. If j is primarily assigned to s (i.e., p js D 1): we do not need to put a replica of

j on s and therefore x js D 0.