Optimal File Sharing in Distributed Networks.
The following file distribution problem is considered: Given  a network of processors represented by an undirected graph  $G=(V,E)$ and a file size $k$, an arbitrary file w  of $k$ bits is to be distributed among all nodes of $G$. To  this end, each node is assigned a memory device such that by  accessing the memory of its own and of its adjacent nodes,  the node can reconstruct the contents of w. The  objective is to minimize the total size of memory in the  network. This paper presents a file distribution scheme  which realizes this objective for $k \gg \log \Delta_G$,  where $\Delta_G$ stands for the maximum degree in $G$: For  this range of $k$, the total memory size required by the  suggested scheme approaches an integer programming lower  bound on that size. The scheme is also constructive in the  sense that given $G$ and $k$, the memory size at each node  in $G$, as well as the mapping of any file w into the  node memory devices, can be computed in time complexity  which is polynomial in $k$ and $|V|$. Furthermore, each node  can reconstruct the contents of such a file w in  $O(k^2)$ bit operations. Finally, it is shown that the  requirement of $k$ being much larger than $\log \Delta_G$ is  necessary in order to have total memory size close to the  integer programming lower bound.
Introduction
Consider the following file distribution problem: A network of processors is represented by
an undirected graph G. An arbitrary file w of a prescribed size k (measured, say, in bits)
is to be distributed among all nodes of G. We are to assign memory devices to the nodes
of G such that, by accessing the memory of its own and of its adjacent nodes, each node
can reconstruct the contents of w. Given G and k, the objective is to find a static memory
allocation to the nodes of G, independent of w, as to minimize the total size of memory in
the network. Although we do not restrict the file distribution or reconstruction algorithms
to be of any particular form, we aim at simple and efficient ones.
The problem of file allocation in a network, i.e., of storing a file in a network so that
every processor has "easy" access to the file, has been considered in many variants (see [4]
for a survey). The specific version of reconstruction from adjacent nodes only has received
attention in the form of file segmentation, where the task is to partition the file so that, for
each node u in the network, the union of the file segments stored at nodes adjacent to u is
the complete file [4][8][13]. As we shall see, allowing more general reconstruction procedures
than simply taking the union of file segments at adjacent nodes can result in a considerable
savings of the total amount of memory required: Letting \Delta G denote the maximum degree of
any node in G, the memory requirement of the best segmentation scheme can
times larger than the optimal requirement in the general scheme; this bound is tight.
We start by deriving linear and integer programming lower bounds on the total size
of memory required for any network G and file size k. We then present a simple scheme
that attains these bounds for sufficiently large values of k. In this scheme, however, the
file size k must be, in some cases, much larger than \Delta G log \Delta G in order to approach the
above-mentioned lower bounds. We regard this as a great disadvantage for two reasons:
such a scheme may turn out to be efficient only for large files, and, even then, it requires
addressing large units of stored data each time a node accesses the file. Thus we devote
considerable attention to the problem of finding a scheme that is close to the linear and
integer programming bounds with file size that is as small as possible.
Our main result is that the critical file size above which the linear or integer programming
bounds can be approached is of the order of log We present a file distribution scheme
for any network G and file size k, of total memory size that is within a multiplicative factor
"(G; k) from the linear programming bound, where "(G; stands for a term which
approaches zero as k= log \Delta G increases. On the other hand, we present an infinite sequence
of network-file-size pairs
such that k l - log \Delta G l , and yet any file distribution
scheme, when applied to a pair (G l ; k l ), requires memory size which is 1
larger than the integer (or linear) lower bound, with lim inf l!1 ffi(G l ; k l
4 . This proves
that a file size of the order of log \Delta G is, indeed, a critical point.
The rest of the paper is organized as follows. In Section 2 we provide the necessary
background and definitions. In Section 3 we describe the linear and integer programming
lower bounds and prove that the linear programming lower bound can be approached for large
file sizes k. In Section 4 we prove our main result, namely, we present a file distribution
scheme that approaches the linear programming bound as the ratio k= log \Delta G increases.
Finally, in Section 5 we exhibit the fact that a file size of log \Delta G is a critical point, below
which there exist infinite families of networks for which the linear and integer programming
lower bounds cannot be attained.
Background and definitions
Throughout this paper we assume the underlying network to be presented by an undirected
graph E), with a set of nodes and a set of edges EG such that -
(i) G does not have parallel edges; and -
(ii) each node contains a self loop. This stands for the fact that each node can access its
own memory.
An undirected graph satisfying conditions (i) and (ii) will be referred to as a network graph.
Two nodes u and v in a network graph E) are adjacent if there is an edge in G
connecting u and v. The adjacency matrix of a network graph E) is the jV j \Theta jV j
are adjacent, and a
Note that, by the definition of a network graph, every node u 2 V is adjacent to itself and,
thus, a
For every \Gamma(u) be the set of nodes that are adjacent to u in G. The degree of u is
denoted by \Delta(u) \Delta
j\Gamma(u)j, and the maximum degree in G is denoted by \Delta G
Two real vectors are said to satisfy the relation y - z if y
for all i. The scalar product y \Delta z of these vectors is defined, as usual, by
real
vector y is called nonnegative if y - 0, where 0 denotes the all-zero vector. By the norm
of a nonnegative vector y we mean the L 1 -norm kyk \Delta
denotes the all-one
vector.
Given a network graph E) and a positive integer k, a file distribution protocol
for (G; intuitively, a procedure for allocating memory devices to the nodes of G, and
to map an arbitrary file w of size k into these memory devices, such that each node u can
reconstruct w by reading the memory contents at nodes adjacent to u.
More precisely, let F 2
E) be a network graph, and let k be a
positive integer. For and a real vector by (AGz) u the uth entry 1
of AGz; this entry is equal to
v2\Gamma(u) z v . A file distribution protocol - for (G; k) is a list
, consisting of -
ffl memory allocation, which is a nonnegative integer vector the entry x u
denotes the size of memory (in bits) assigned to node u;
encoding mappings
2 for every
these mappings define the coding rule of any file w of size k into the memory devices
at the nodes: the contents of the memory at node u is given by E u (w);
ffl decoding (reconstruction) mappings
2 for every
The memory allocation, encoding mappings, and decoding mappings satisfy the requiremen

D u
1 As we have not defined any order on the set of nodes V , the order of entries in vectors such as z can be
fixed arbitrarily. The same applies to rows and columns of the adjacency matrix AG , or to subvectors such
as [z v ] v2\Gamma(u) .
Equation (1) guarantees that each node u is able to reconstruct the value (contents)
of any file w of size k out of the memory contents E v (w) at nodes v adjacent to u.
The memory size of a file distribution protocol
for (G;
defined as the norm kxk and is denoted j-j. That is, the memory size of a file distribution
protocol is the total number of bits assigned to the nodes. The minimum memory size of
any file distribution protocol for (G; k) is denoted by M(G; k).
Example 1. The file segmentation method mentioned in Section 1 can be described as
a file distribution protocol for (G; associated
encoding mappings
2 of the form
k. For a node u 2 V to be able to reconstruct
the original file w, the mappings E v , v 2 \Gamma(u), must be such that every entry w i of w appears
in at least one E v (w). This implies that the set of nodes S i which w i is mapped to under the
encoding mappings must be a dominating set in G; that is, each node u 2 G is adjacent to
some node in S i . On the other hand, given a dominating set S in G, we can construct a file
segmentation protocol for (G; of memory size k \Delta jSj - k \Delta jV j (the case corresponds
to simply replicating the original file w into each node in G). ffl
A file distribution scheme is a function (G; -(G; which maps every network graph
G and positive integer k into a file distribution protocol -(G;
A file distribution scheme (G;
is constructive if -
(a) the complexity of computing the memory allocation x is polynomial in k and jV j;
(b) for every w 2 F k
2 , the complexity of computing the encoded values [ E u (w) ] u2V is polynomial
in the memory size kxk; and -
(c) for every
2 , the complexity of reconstructing out of c
is polynomial in the original file size k.
By computational complexity of a problem we mean the running time of a Turing machine
that solves this problem.
Remark 1. In the definition of memory size of file distribution protocols we chose not
to count the amount of memory required at each node u to store and run the routines which
implement the decoding mappings D u (\Delta). The reasoning for neglecting this auxiliary memory
is that, in practice, there are a number of files (each, say, of the same size k) that are to be
distributed in the network. The file distribution protocol can be implemented independently
for each such file, using the same program and the same working space to handle all these
files. To this end, we might better think of k as the size of the smallest information unit
(e.g., a word, or a record) that is addressed at each access to any file. From a complexity
point of view, we would prefer k to be as small as possible. The motivation of this paper
can be summarized as finding a constructive file distribution scheme (G; -(G;
maintains a ratio of memory-size to file-size virtually equal to lim l!1 M(G; l)=l for relatively
small file sizes k. ffl
Remark 2. One might think of a weaker definition for constructiveness by allowing
non-polynomial pre-computation of x (item (a)) and, possibly, of some other data structures
which depend on G and k, but not on w (e.g., calculating suitable representations for E u
and D u ); such schemes may be justified by the assumption that these pre-computation steps
should be done once for a given network graph G and file size k. On the other hand, items
(b) and (c) in the constructiveness definition involve the complexity of the more frequent
occasions when the file is encoded and - even more so - reconstructed. In this paper,
however, we aim at finding file distribution schemes which are constructive in the way we
have defined, i.e., in the strong sense: satisfying all three requirements (a)-(c). ffl
We end this section by introducing a few terms which will be used in describing the
mappings E u and D u of the proposed file distribution schemes. Let \Phi be a finite alphabet of
q elements. An (n; K) code C over \Phi is a nonempty subset of \Phi n of size K; the parameter n
is called the length of C, and the members of C are referred to as codewords. The minimum
distance of an (n; K) code C over \Phi is the minimum integer d such that any two distinct
codewords in C differ in at least d coordinates.
Let C be an (n; K) code over \Phi and let S be a subset of hni \Delta
ng. We say that
C is separable with respect to S if every two distinct codewords in C differ in at least one
coordinate indexed by S. The next lemma follows directly from the definition of minimum
distance.
Lemma 1. The minimum distance of an (n; K) code C over \Phi is the minimum integer
d for which C is separable with respect to every set S ' hni of size n \Gamma d + 1.
Let q be a power of a prime. An (n; K) code C over a field
is a linear subspace of \Phi n ; in this case we have is the dimension of C. A
generator matrix B of a linear (n; q k ) code C over \Phi is a k \Theta n matrix B over \Phi whose rows
span the codewords of C.
For a k \Theta n matrix B (such as a generator matrix) and a set S ' hni, denote by (B) S the
k \Theta jSj matrix consisting of all columns of B indexed by S. The following lemma is easily
verified.
Lemma 2. Let C be an (n; q k ) linear code over a field \Phi, let B be a generator matrix of
C, and let S be a subset of hni. Then, C is separable with respect to S if and only if (B) S
has rank k.
3 Lower bounds and statement of main result
In this section we first derive lower bounds on M(G; k), i.e., on the memory size of any
file distribution protocol for (G; k). Then, we state our main result (Theorem 2) which
establishes the existence of a constructive file distribution scheme (G;
attains these lower bounds whenever k AE log \Delta G . As the proof of Theorem 2 is somewhat
long, it is deferred to Section 4. Instead, we present in this section a simple file distribution
scheme which attains the lower bounds when k
log \Delta G ).
3.1 Lower bounds
u2V be a memory allocation of some file distribution protocol for (G; k). Assigning
x u bits to each node u 2 V , each node must "see" at least k memory bits at its adjacent
nodes, or else (1) would not hold. Therefore, for every u 2 V we must have
or, in vector notation,
Let J(G; denote the minimum value attained by the following integer programming
problem:
J(G;
IP(G; ranging over all integer y such that
Also, let ae G denote the minimum value attained by the following (rational) linear programming
problem:
ranging over all rational z such that
(2)
The next theorem follows from the previous definitions, Example 1, and the fact that
J(G; 1) is the size of a (smallest) dominating set in G.
Theorem 1. For every network graph G and positive integer k,
We call J(G; k) the integer programming bound, whereas ae G \Delta k is referred to as the linear
programming bound.
For 1). The problem of deciding whether a
network graph G has a dominating set of size - s is well-known to be NP-complete [6]. The
next corollary immediately follows.
Corollary 1. Given an instance of a network graph G and positive integers k and s, the
problem of deciding whether there exists a file distribution protocol for (G; of memory
size - s (i.e., whether M(G;
Note that we do not know whether the decision problem of Corollary 1 is in NP (and
therefore, whether it is NP-complete) since it is unclear how to verify (1) in polynomial-time,
even when the encoding and decoding mappings are computable in polynomial-time.
Remark 3. A result of Lov'asz [11] states that J(G; 1) - ae G log 2 \Delta G ; on the other hand,
one can construct an infinite family of network graphs fG l g l (such as the ones presented in
Section 5) for which J(G l ;
(see also [7]). In terms of file segmentation
schemes (Example 1) this means that there always exists a file distribution protocol for (G;
based on segmentation whose memory size, k \Delta J(G; 1), is within a multiplicative factor of
log 2 \Delta G from the linear programming bound ae G \Delta k. Yet, on the other hand, there are families
of network graphs for which such a multiplicative gap is definitive (up to a constant 4), even
when k tends to infinity. ffl
3.2 Statement of main result
Corollary 1 suggests that it is unlikely that there exists an efficient algorithm for generating
a file distribution scheme (G; M(G; k). This directs
our objective to finding a constructive file distribution scheme (G; -(G; k) such that
j-(G; k)j =(ae G \Delta k) is close to 1 for values of k as small as possible.
More specifically, we prove the following theorem.
Theorem 2. There exists a constructive file distribution scheme (G;
that
j-(G; k)j
log
s
log
(The maximum in the right-hand side of (3) is determined according to whether k is smaller,
or larger, than log \Delta G . Also, by Theorem 1, the ratios j-(G; k)j =M(G; k), M(G; k)=J(G; k),
and J(G; k)=(ae G \Delta
In Section 4 we prove Theorem 2 by presenting an algorithm for generating a constructive
file distribution scheme (G; -(G; which satisfies (3); in particular, the computational
complexity of the encoding mappings in the resulting scheme (item (b) in the constructiveness
requirements) is O(k \Delta j-(G; k)j), whereas applying the decoding mapping at each node (item
operations. Returning to our discussion in Remark 1, the complexity
of these mappings suggests that the file size k should be as small as possible, still greater
than log \Delta G . This means that files distributed in the network should be segmented into
records of size k = a \Delta log \Delta G for some (large) constant a, each record being encoded and
decoded independently. Information can be retrieved from the file by reading whole records
of size a \Delta log \Delta G bits each, requiring O(a 2 log 2 \Delta G ) bit operations, whereby the ratio between
the memory size required in the network and the file size k is at most 1
a) times
that ratio for k !1.
Our file distribution algorithm is divided into two major steps:
Step 1. Finding a memory allocation by finding an approximate
solution to an integer programming problem; the resulting memory size j-(G;
will satisfy (3).
Step 2. Constructing a set of k \Theta x u matrices B u , these matrices define
the encoding mappings
. The choice of the
matrices B u , in turn, is such that each k \Theta (AGx) u matrix [B v ] v2\Gamma(u) is of rank k, thus
yielding decoding mappings D
which satisfy (1).
3.3 File distribution scheme for large files
In this section we present a fairly simple constructive file distribution scheme (G;
-(G;
j-(G; k)j
Note that this proves Theorem 2 whenever k
log \Delta G ).
Given a network graph E) and a positive integer k, we first compute a memory
allocation be an optimal solution to the
linear programming problem LP(G) in (2). Such a vector z can be found in time complexity
which is polynomial in jV j (e.g., by using Karmarkar's algorithm [9]). Set h \Delta
and l \Delta
dk=he, and define the integer vector
y u
Clearly, furthermore, since AGz - 1, we also have
(AGy)
i.e., AGy - l \Delta 1. The memory allocation for (G; k) is defined by x \Delta
y, and it is easy to
verify that kxk=(ae G \Delta
We now turn to defining the encoding and decoding mappings (Step 2 above). To this
end, we first assign \Delta G \Delta l colors to the nodes of G, with each node u assigned a set C u of y u
colors, such that
In other words, we multi-color the nodes of G in
such a way that each node "sees" at least l colors at its adjacent nodes.
Such a coloring can be obtained in the following greedy manner: Start with C u / ; for
every Call a node u saturated if
l (hence, at the beginning all nodes are
unsaturated, whereas at the end all should become saturated). Scan each node u 2 V once,
and, at each visited node u, re-define the set C u to have y u distinct colors not contained in
sets C v already assigned to nodes v 2 \Gamma(u 0 ) for all unsaturated nodes u
To verify that such a procedure yields, indeed, an all-saturated network, we first show
that at each step there are enough colors to assign to the current node. Let oe(u) denote the
number of unsaturated nodes u being re-defined. Recalling that
l for every v 2 V , it is easy to verify that the number of disqualified colors for C u is
at most oe(u) This leaves at least
y u qualified colors to assign to node u. We now claim that each node becomes saturated at
some point. For if node u remained unsaturated all along, then the sets C v , v 2 \Gamma(u), had
to be disjoint; but in that case we would have
y
contradicting the fact that u was unsaturated.
\Deltal be distinct elements in \Phi \Delta
corresponding to some
color j (note that j\Phij - Given a file w of k bits, we group the entries
of w into h-tuples to form the coefficients of a polynomial w(t) of degree
\Phi. We now compute the values w and store at each node u
the values w requiring memory allocation of x each u has
access to images w j of w(t) evaluated at l distinct elements each node can interpolate
the polynomial w(t) and, hence, reconstruct the file w.
The above encoding procedure can be described also in terms of linear codes (refer to
the end of Section 2). Such a characterization will turn out to be useful in Sections 4
and 5. Let B RS be an l \Theta (\Delta G l) matrix over defined by (B RS
l. For every node u 2 V , let C u be the set of colors assigned to u
and let B u
regarding C u as a subset of f1; consists of all
columns of B RS indexed by C u . The mappings
are defined by E . The matrix B RS is known as a generator
matrix of a Chs. 10-11]. Note that
since every l columns in B RS are linearly independent, every l \Theta (AGy) u matrix [B v ] v2\Gamma(u)
has rank l, allowing each node u to reconstruct w out of [wB v ] v2\Gamma(u) .
We remark that Reed-Solomon codes have been extensively applied to some other reconstruction
problems in networks, such as Shamir's secret sharing [18] (see also [10][14]).
The file distribution scheme described in this section is not satisfactory when the file size
which case the ratio -(G; k)=(ae G \Delta might be bounded away from 1.
This will be rectified in our next construction which is presented in Section 4.
4 Proof of main result
In this section we present a file distribution scheme which attains the memory size stated
in Theorem 2. In Section 4.1 we present a randomized algorithm for finding a memory
allocation by scaling and perturbing a solution to the linear programming problem LP(G)
defined in (2). Having found a memory allocation x, we describe in Section 4.2 a second
randomized algorithm for obtaining the encoding and decoding mappings. Both algorithms
are then de-randomized in Section 4.3 to obtain a deterministic procedure for computing
the file distribution scheme claimed in Theorem 2. In Section 4.4 we present an alternative
proof of the theorem using the Lov'asz Local Lemma. In Section 4.5 we consider a variant of
the cost measure used in the rest of the paper: instead of looking for a near optimal solution
with respect to the total memory requirement of the system, we consider approximating the
best solution such that the maximum amount of memory required in any node is close to
the minimum feasible. This is done using the techniques of Section 5.
4.1 Step 1. Solving for a memory allocation
The goal of this section is to prove the following (hereafter e stands for the base of natural
logarithms).
Theorem 3. Given a network graph G and an integer m, let z = [z u ] u2V be a nonnegative
real vector satisfying AGz - 1. Then there is a nonnegative integer vector x satisfying
log e \Delta G
s
log e \Delta G
for some absolute constant c.
In fact, we provide also an efficient algorithm to compute the nonnegative integer vector
guaranteed by the theorem. The vector x will serve as the memory allocation
of the computed file distribution protocol for an instance (G; k), where we will need to
take m slightly larger than k in order to construct the encoding and decoding mappings in
Section 4.2.
Theorem 3 is proved via a 'randomized rounding' argument (see [15][17]): We first solve
the corresponding linear programming problem LP(G) in (2) (say, by Karmarkar's algorithm
[9]), and use the rational solution to define a probability measure on integer vectors
that are candidates for x. We then show that this probability space contains an integer
vector x which satisfies the conditions of Theorem 3. Furthermore, such a vector can be
found by a polynomial-time (randomized) algorithm. Note that if we are interested in a
weaker result, where log jV j replaces log \Delta G in Theorem 2 (or in Theorem 3), then a slight
modification of Raghavan's lattice approximation method can be applied [15]. However,
to prove Theorem 3 as is, we need a so-called 'local' technique. One possibility is to use
the 'method of alteration' (see [19]) where a random integer vector selected from the above
probability space is perturbed in a few coordinates so as to satisfy the conditions of the
theorem. Another option is to use the Lov'asz Local Lemma. Both methods can be used
to prove Theorem 3, and both can be made constructive and deterministic: the method of
alteration by applying the method of conditional probabilities (see Spencer [19, p. 31] and
Raghavan [15]), and the Local Lemma by using Beck's method [2]. We show here the method
of alteration, and present a second existence proof using the Local Lemma in Section 4.4.
Given a nonnegative real vector and a real number ' ? 0, define the vectors
s u
note that 0 - p u2V be a random vector of independent
random variables Y u over f0; 1g such that
Y
and let u2V be a random vector defined by
Fix a to be a real vector in the unit hyper-cube [0; 1] jV j such that a \Delta z - 1. Since the
expectation vector E
Y
is equal to p, we have
a
In particular, if z is a rational vector satisfying AGz - 1, then
Showing the existence of an instance of X which can serve as the desired memory allocation
x makes use of the following two propositions. The proofs of these propositions are
given in the Appendix, as similar statements can be found also in [15].
Throughout this section, Lffi; jg stands for max
log e fi ;
Proposition 1. Given a nonnegative real vector z and an integer ', let
be defined by (5)-(7), let a be a real vector in [0; 1] jV j such that a \Delta z - 1, and let m be a
positive integer. There exists a constant c 1 such that, for every fi - 1,
a
Proposition 2. Given a nonnegative real vector z and an integer ', let
defined by (5)-(7) and let a be a real vector in [0; 1] jV j . There exists a constant c 2 such that,
for every fi - 1,
a
a
a
joo
Consider the following algorithm for computing a nonnegative integer vector x for an
instance (G; m):
Algorithm 1.
1. Set
G and mg.
2. Solve the linear programming problem LP(G) (defined by (2)) for z.
3. Generate an instance of the random vector (5)-(7).
4. The integer vector
x u
Theorem 3 is a consequence of the following lemma.
Lemma 3. The vector kxk obtained by Algorithm 1 satisfies Inequality (4) with probability
Proof. Call a node v deficient if (AGX) for the generated vector X. First note
that x u is either X u or X u that
in fact, for deficient nodes v we have (AGx) v - ' \Delta (AGz) v - m.
Now, by Proposition 1, for every node v 2 V ,
node v is deficient
Hence, for each node u
x
node v is deficient
Therefore, the expected number of nodes u for which x 1 is at most jV j
and, with
probability at least 1
2 , there are no more than jV j
such nodes u. Observing that
(AGz)
we thus obtain, with probability - 1,
Recalling that E
apply Proposition 2 with
Hence, by (8), (9), and (10) we conclude that, with probability - 1
, the integer
vector x satisfies both
and
The last inequality implies
s
log e fi G
and the lemma now follows by substituting
log e fi G
s
log e fi G
;A
and
G in (12).
Note that for
log
s
log
(compare with the right-hand side of (3)). The vector x, computed for
will serve, with a slight modification, as the memory allocation of -(G; k). In Section 4.3 we
shall apply the method of conditional probabilities to make Algorithm 1 deterministic.
4.2 Step 2. Defining the encoding mappings
Having found a memory allocation x, we now provide a randomized algorithm for constructing
the encoding and decoding mappings. The construction makes use of the following
lemma.
Lemma 4. [12, p. 444]. Let S denote a random matrix, uniformly distributed over all
matrices over F 2 . Then,
Given an instance (G; k), let u2V be the nonnegative integer vector obtained by
Algorithm 1. The following algorithm computes for each node
u a matrix B u to be used for the encoding mappings.
Algorithm 2.
1. For each u 2 V , assign at random a matrix Q u uniformly distributed over all k \Theta x u
matrices over F 2 .
2. For each
define the encoding matrix B u by
I k if rank (S u
where I k stands for the k \Theta k identity matrix.
Note that each B u is a k \Theta -
x u binary matrix with
x
x
The vector -
serve as the (final) memory allocation for -(G; k). As we
show later on in this section, the excess of k- xk over kxk, if any, is small enough to let
Equation hold also with respect to the memory allocation - x. This will establish the
memory size claimed in Theorem 2. The associated encoding mappings
are
given by E and the overall process of encoding w into [ E
requires O(k \Delta k- xk) multiplications and additions over F 2 .
Recalling the definitions in Section 2, note that for each node u, the k \Theta k- xk matrix
separable with respect to the set \Gamma(u); that is, the rank of (B)
is k. Therefore, each node u, knowing the values [ is able to
reconstruct the file w. To this end, node u has to process only k fixed coordinates of
w(B) \Gamma(u) , namely, k coordinates which correspond to k linearly independent columns of
Let such a set of coordinates be indexed by the set T u , Assuming a 'hard-
wired' connection between node u and the k entries of w(B) \Gamma(u) indexed by T u , the decoding
process at u sums up to multiplying the vector w(B) Tu 2 F k
2 by the inverse of (B) Tu . Hence,
the mappings D u , are given by D u
. The
decoding process at each node thus requires O(k 2 ) multiplications and additions over F 2 .
Note that in those cases where we set B u in (14) to be the identity matrix, the decoding
process is trivial, since the whole file is written at node u.
We now turn to estimating the memory size -
x. First note that for every node u, the
matrix S u is uniformly distributed over all k \Theta (AGx) u matrices over F 2 . Recalling that, by
construction, (AGx)
rank (S u
G
Hence, the expected number of nodes for which -
in (15) is at most jV j
Therefore, with probability at least 1
2 , there are no more than jV j
G nodes u whose memory
allocation x u has been increased to -
x
G , the total memory-size
increase in (15) is bounded from above by
G )kzk. Hence, by (13),
k- xk
G )kzk
log
s
log
;A
log \Delta G ). Recall that the construction of Section 3.3 covers Theorem 2
for larger values of k.
In Section 4.3 we apply the method of conditional probabilities (see [19, p. 31] and [15])
in order to make the computation of the matrices B u deterministic.
Remark 4. It is worthwhile comparing the file distribution scheme described in Sections
4.1 and 4.2 with the scheme of Section 3.3, modified to employ Algorithm 1 on
(G; dk=he), k)e, to solve for the memory allocation there. It can be verified
that the resulting file distribution scheme is slightly worse than the one obtained here:
every term log \Delta G in (3) should be changed to log(\Delta G \Delta In particular, this method
has critical file size of log 2 \Delta G . ffl
4.3 A deterministic algorithm
We now show how to make Algorithms 1 and 2 deterministic using the method of conditional
probabilities of Spencer [19, p. 31] and Raghavan [15], adapted to conditional expectation
values. The idea of the method of conditional probabilities is to search the probability space
defined by the random choices. At each iteration the probability space is bisected by setting
one of the random variables. Throughout the search we estimate the probability of success,
conditional on the choices we have fixed so far. The value of the next random variable is
chosen as the one that maximizes the estimator function.
In de-randomizing Algorithms 1 and 2 we employ as an estimator the expected value of
the size of the allocation. At every step the conditional expectation for both possibilities for
the value of the next random variable are computed and the setting that is smaller (thus
increasing the probability of success) is chosen. Unlike Raghavan [15], we do not employ a
"pessimistic estimator," but rather a conditional expectation estimator which is fairly easy
to compute.
We start with de-randomizing the computation of the (initial) memory allocation x. Let
be the vectors computed in the course
of Algorithm 1. Recall that for every u 2 V , the entry X u is a random variable given by
x
node u is deficient
We refer to -
E as the expectation estimator for x, and we have,
Comparing the last inequality with (12), it would suffice if we found a memory allocation
whose size is at most -
E. Note that -
can be computed efficiently by calculating the expressions
for subsets W i of \Gamma(u) consisting of the first i nodes in \Gamma(u) for
s m. Such a computation can be carried
out efficiently by dynamic programming.
the first entry of define the conditional expectation
estimators by
Indeed, we have E
furthermore, the two conditional expectation
estimators -
E as a convex combination and, therefore, one of them must be
bounded from above by -
E. We set the entry Y 1 to the bit y
b is the smallest.
Note that, like -
E, the conditional expectation estimators can be efficiently computed.
Having determined the first entry in Y, we now re-iterate this process with the second
now involving the conditional expectation estimators -
Continuing
this way with subsequent entries of Y, we end up with a nondecreasing sequence of
conditional expectation estimators
thus determining the whole vector Y, and therefore the vectors X and x, the latter having
memory size - ('
We now turn to making the computation of the encoding mappings deterministic. Recall
that Algorithm 2 first assigns a random k \Theta x u matrix Q u to each node u. We may regard
this assignment as an kxk-step procedure, where at the nth step a random column of F k
2 is
added to a node v with less than x v already-assigned columns. Denote by Q u;n the (partial)
matrix at node u 2 V after the nth step. The assignment of the random matrices Q u
to the nodes of the network can thus be described as a random process fU n g kxk
u2V is a random column configuration denoting the contents of each node after
adding the nth column to the network graph. We shall use the notation U 0 for the initial
column configuration where no columns have been assigned yet to any node.
Let S u denote the random matrix [Q v ] v2\Gamma(u) (as in Algorithm 2) and let R be the number
of nodes u for which rank (S u k. Recall that Algorithm 2 was based on the inequality
E(R) \Delta
which then allowed us to give a probabilistic estimate of 2E(R) ! jV j
for the number of
nodes u that required replacing Q u by I k . Instead, we compute here a sequence of column
configurations U kxk, such that
in particular, we will have
i.e., the number of nodes u for which B u is set to I k in (14) is guaranteed to be less than
In order to attain the inequality chain (16) we proceed as follows: Let U 0 be the empty
column configuration and assume, by induction, that the column configuration U n\Gamma1 has been
determined for some n - 1. Let v be a node which has been assigned less than x v columns
in U n\Gamma1 . We now determine the column which will be added to v to obtain U n . This is done
in a manner similar to the process described before for de-randomizing Algorithm 1: Set the
first entry, b 1 , of the added column to be 0, assume the other entries to be random bits, and
compute the expected value, E 0 , of R conditioned on U
repeat the process with b 1 being set to 1, resulting in a conditional expected value E 1 of R.
Since the two conditional expected values E 0 and E 1 average to E(R j U
of them must be at most that average. The first entry b 1 in the column added to v is set
to the bit b for which E b is the smallest. This process is now iterated for the second bit b 2
of the column added to v, resulting in two conditional expected values
the smaller of which determines b 2 . Continuing this way, we obtain a sequence of conditional
expected values of R,
E(R j U
thus determining the entire column added to v. Note that, indeed,
in accordance with (16).
It remains to show how to compute the conditional expected values of R which are used
to determine the column configurations U n . It is easy to verify that, for any event A,
E(R
rank (S u
Hence, the computation of the conditional expected values of R boils down to the following
problem:
Let S denote a k \Theta m random matrix over F 2 whose first l columns, as well as the first t
entries in its (l 1)st column, are preset, and the rest of its entries are independent random
bits with probability 1of being zero. What is the probability of S having rank k?
Let H denote the k \Theta l matrix consisting of the first l (preset) columns of such a random
matrix S. Denote by T the matrix consisting of the first l columns of S and by W the
matrix consisting of the last columns of S. Also, let the random variable ae denote
the rank of T. Clearly, ae may take only two values, namely, rank (H) or rank (H) + 1. We
now show that
Indeed, without loss of generality assume that the first r rows of T are linearly independent.
We assume that the entries of W are chosen randomly row by row. Having selected the first
r rows of W, we thus obtain the first r rows in S which, in turn, are linearly independent.
Next we select the (r 1)st row in W. Clearly, there are 2 choices for such a row, out
of which one row will result in an (r 1)st row in S which is spanned by the first r rows
in S. Hence, given that the first r rows in W have been set, the probability that the first
rows in S will be linearly independent is Conditioning upon the linear
independence of the first r in S, we now select the (r + 2)nd row in W. In this case
there are two choices of this row that yield an (r+2)nd row in S which is spanned by the first
r +1 rows in S. Hence, the probability of the first r +2 rows in S to be linearly independent
(given the linear independence of the first r In general, assuming
linear independence of the first r in S, there are 2 i choices for the (r 1)st
row of W that yield a row in S belonging to the linear span of the first r
The conditional probability for the first r rows in S to be linearly independent thus
Equation (18) is obtained by re-iterating the process for all rows of
W.
To complete the computation of the probability of S having rank k, we need to calculate
the probability of ae being denote the first t rows of H with r t
denote the first t (preset) entries of the (l 1)st column of S (or of T).
We now show that
We first perform elementary operations on the columns of H so that (i) the first r t columns
in H t are linearly independent whereas the remaining l \Gamma r t columns in H t are zero, and
(ii) the first r columns in H are linearly independent whereas the remaining l \Gamma r columns
in H are zero. Now, if c is not in the linear span of the columns of H t , then
1. Otherwise, there are 2 r\Gammar t ways to select the last entries of the (l 1)st
column of T to have that column spanned by the columns of H: each such choice corresponds
to one linear combination of the last r \Gamma r t nonzero columns of H. Therefore, conditioning
upon rank ([H t ; the probability of having rank (T
Equations (18) and (19) can be now applied to S u to compute the right-hand side of (17),
where A stands for the event of having columns in U n set to U n\Gamma1 , and t bits of the
currently-added nth column set to b 1
4.4 Proof using the Lov'asz Local Lemma
In this section we present an alternative proof for the existence of a memory allocation
x satisfying (3) and of k \Theta x u binary matrices B u for the encoding mappings E
. The techniques used will turn out to be useful in Section refvariations. To
this end, we make use of the following lemma.
Lemma 5 . (The Lov'asz Local Lemma [5][19]). Let A 1 ; A be events in an
arbitrary probability space. Suppose that each event A i is mutually independent of a set of
all, but at most ffi, events A j and that Prob fA i
In most applications of the lemma (as well as in its use in the sequel), the A i 's stand for
'bad' events; hence, if the probability of each bad event is at most p, and if the bad events
are not-too-dependent of one another (in the sense stated in the lemma), there is a strictly
positive probability that none of the bad events will occur. However, this probability might
be exponentially small. Recently, Beck [2] has proposed a constructive technique that can
be used in most applications of the lemma for finding an element of
We shall be mainly concentrating on an existence proof, as the construction will then follow
by a technique similar to the one in [2].
We start by using the local lemma to present an alternative proof of Theorem 3. Given
a network graph and an integer m, we construct a directed graph
which satisfies the following four properties:
(i) there is an edge whenever u is adjacent to v in G;
(ii) there are no parallel edges in H;
(iii) each node in H has the same in-degree \Delta
(iv) each node in H has an out-degree which is bounded from above by
Lemma 6. A directed graph H satisfying (i)-(iv) always exists.
Proof. When
as the complete graph (i.e., the adjacency matrix
AH is the all-one matrix and Otherwise, we construct H out of G
as follows: Make every self loop in G a directed edge in H, and change all other edges in G
into two anti-parallel edges in H. Finally, adjoin extra edges (not parallel to existing ones)
to have in-degree G at each node in H. To realize
this last step, we scan the nodes of H and add incoming edges to nodes whose in-degree is
less than \Delta G - one node at a time. Let u be such a node and let \Gamma(u) be the set of nodes
in H with no outgoing edges that terminate at u. We show that at least one of the nodes
in \Gamma(u) has out-degree less than 2\Delta G , thus allowing us to adjoin a new incoming edge to
u from that node. The proof then continues inductively. Now, since the in-degree of each
node in H at each stage is at most \Delta G , the total number of edges outgoing from nodes in
\Gamma(u) is bounded from above by 1). On the other hand, \Gamma(u) contains at least
nodes. Hence, there exists at least one node in \Gamma(u) whose out-degree is at most
this number, in turn, is less than
Proof of Theorem 3 using the Local Lemma. Let z be a solution the linear programming
problem LP(G) of (2). By property (i), z satisfies the inequality AH z - 1. Re-define
fi G to be
G (and ' accordingly to be m+c 1 \Delta Lffi G ; mg), and let X be obtained by (5)-(7).
By Proposition 1 we have
and by property (ii) and Proposition 2 we have,
for each node u 2 V .
For every define the event A u as
A u
or
By (20) and (21) it follows that Prob fA u
G ). For every node u in H,
denote by \Gamma out (u) the set of terminal nodes of the edges outgoing from u in H. Then, for every
node u, the event A u is mutually independent of all events A v such that \Gamma out (u)" \Gamma out
Hence, by properties (iii) and (iv), each A u depends on at most   H
G
events A v and, therefore, by Lemma 5 there exists a nonnegative integer vector x satisfying
both
(AGx)
and
for all
We now show that kxk satisfies the inequality
s
log e fi G
By (24) and the fact that each node in H has in-degree \Delta H we have,
(AHx) u
log e
Now, by the Cauchy-Schwarz inequality,
(AH z) u -
and, therefore,
log e
s
Inequality (25) is now obtained by bounding jV j =\Delta H from above by kzk. Finally, Theorem 3
is a consequence of both (23) and (25).
We now turn to defining the encoding and decoding mappings for a given instance (G; k).
To this end, we shall make use of the following lemma.
Lemma 7 . Let S 1 be subsets of hni \Delta
ng, each S i of size - s,
and no subset intersects more than ffi subsets. Let q be a power of a prime and let k be a
nonnegative integer satisfying
Then there exists an (n; q k ) linear code over which is separable with respect to
each S i .
Proof. We construct inductively l \Theta n matrices B l , 1 - l - k, each generating a linear
code which is separable with respect to every S i ; that is, each (B l ) S i has rank l. Start with
an all-one 1 \Theta n matrix B 1 . As the induction step, assume that a matrix B l\Gamma1 , with the
above property, has already been constructed for some l - k. We are now to append an lth
row to B l\Gamma1 .
Given such a matrix B l\Gamma1 , a row vector in \Phi n is 'good' with respect to S i if, when
appended to B l\Gamma1 , it yields a matrix B l such that (B l ) S i has rank l; otherwise, a row vector
is 'bad' with respect to that S i . Now, for each i, the row span of (B consists of q
vectors in \Phi jS this means that the probability of a randomly selected row to be bad with
respect to S i is q \GammajS i Similarly, if S i
then the probability
of a randomly selected row to be bad with respect to both S i and S j is q \GammajS i j\GammajS j j+2(l\Gamma1) .
Therefore, when S i
;, the events "the row vector is bad with respect to S i " and "the
row vector is bad with respect to S j " are independent; thus, by Lemma 5 we are guaranteed
to have a row vector in \Phi n which is good with respect to every S i . This vector can now be
appended to B l\Gamma1 to obtain a generator matrix B l with (B l ) S i having rank l for all i.
Let x be the integer vector guaranteed by Theorem 3 for Partition
the set hkxki into jV j (disjoint) subsets Q u with jQ
We have jS
Furthermore, each S u intersects at most
exists a linear which is separable with respect to each S u . For each
is the k \Theta x u matrix consisting of all columns of B indexed
by Q u . We now use this to define the encoding and decoding mappings as in Section 4.2.
4.5 Variations on the memory cost measure
The techniques used in Section 4.4 can be adapted to obtain file distribution schemes
(G; -(G; which are close to optimal with respect to other variants of the memory
cost measure. For instance, consider the problem where for every instance (G; k), we
are looking for a file distribution protocol -(G; whose memory allocation x satisfies the
following two criterions:
(i) The largest component x max of x is the smallest possible.
(ii) Among all file distribution protocols that satisfy (i), we take one whose memory size
kxk is the smallest.
This variant of our original problem might suit cases where, say, each node in the network
graph (as opposed to some 'network manager') needs to pay for its own memory. Since
the respective decision problem is NP-complete, we need to look for approximations to the
optimal solution.
Given a network graph E) and an integer k, we proceed as follows. Let \Delta min be
min u2V \Delta(u). It is clear that dk=\Delta min e is a lower bound on the largest component of x. Set
and consider the following linear program:
ae
ranging over all rational u2V such that
Next, we set fi
mg. Now, let
obtained by (5)-(7) and re-define the events A u in (22) as
A u
or
or
By (20) and (21) we have Prob fA u
Following along the lines of
Section 4.4, the Lov'asz Local Lemma now guarantees a file distribution protocol with memory
allocation x whose maximal component x max and size kxk satisfy both
log
s
log
;A
and
ae G;ff \Delta k
log
s
log
Both x max and kxk approach there optimal values as k becomes larger than log \Delta G .
5 The integer programming bound is not tight
In Section 4 we presented an algorithm for finding a constructive file distribution scheme
(G; such that the ratio between the memory size j-(G; k)j and ae G \Delta k approaches
1 as the ratio k= log \Delta G tends to infinity. In this section we present a family of network graphs
l=1 for which a file size of log \Delta G l is, indeed, a critical point: there exists a sequence of
file sizes k l - log 2 \Delta G l , which the ratios M(G l ; k l )=J(G l ; k l ) (and, therefore,
are bounded away from 1.
For integers m and l, m - l, define the network graphs G
Let Um be a set of m elements (say, consist of all subsets of Um of
size l. Set V draw an edge between two nodes in any of the
following cases: (i) both u and v are in Um (i.e., Um is a clique); (ii) u 2 Um , v 2 W m;l , and
loops).
First, we verify that ae G m;l
be a nonnegative real vector satisfying
AG m;l
loss of generality, we can assume that z
otherwise, "remove" the quantity z v from such a node v and add it to the value
z u at some node u 2 \Gamma(v) \Gamma fvg ' Um . This change results in a new nonnegative vector ~ z
with the same norm as z and which satisfies AG m;l
~ z - 1.
Now, rename the nodes of Um to have . For the node
l
z
AG m;l
z
and, therefore, z u - z l - 1=l for every node u - l in Um . Hence,
ae G
l
z
z
l
Setting to
z
1=l if u 2 Um
we obtain the equality ae G
for every positive integer r. A similar analysis for a similar set-covering problem appears
also in [7].
In the forthcoming discussion we will be concentrating on two types of network graphs
G m;l , namely:
, in which case ae G
l ;l , in which case ae H
The proof of the next proposition makes use of the following known lemma.
Lemma 8 . (The sphere-packing or the Hamming bound [12, Ch. 1]). Let \Phi be an
alphabet of q elements. There exists an (n; K) code of minimum distance 2t
if
Proposition 3. For any fixed positive integer r,
lim
ae G l
Proof. Set positive integer r and let x be the memory allocation of a
file distribution protocol - for (G l ; of memory size We assume
that x and that the nodes of U are renamed to have
Letting h \Delta
where the inequality follows from P l
in turn, implies the
inequalities x l+1 - x l - r.
For a file w
denote the encoded memory contents [ E
u=1 as determined
by the file distribution protocol -. We now regard the set
cw
as an (l over an alphabet of q \Delta
elements. The code C must be separable
with respect to any subset of hl +2i of size l, or else there would be nodes in W 2l;l that could
not reconstruct the file w. Hence, by Lemma 1, the minimum distance of C is at least 3,
which readily implies by Lemma 8 the inequality
Substituting noting that 2
(l
or
log
log
Hence, for fixed r and for sufficiently large l we must have 1. Combining this lower
bound on h with (28) yields the inequality
lim
which, with (27), concludes the proof.
Corollary 2. For k l
lim
ae G l \Delta k l
Corollary 2 exhibits the fact that a file size of log \Delta G l is a critical point in the following
strong sense: For k l = 2l - log 2 \Delta G l , the size of any memory allocation for (G l ; k l ) must be
bounded away from ae G l
l , not because of a gap between J(G l ; k l ) and ae G l
l , but rather
because of a gap between M(G l ; k l ) and J(G l ; k l ).
We point out that, as a counterpart of Proposition 3, we also have
lim
the proof of which is based on the following result.
Lemma 9. (The Gilbert-Varshamov bound [3, pp. 321-322]). Let \Phi be an alphabet of
q elements and let n, K, and d be positive integers satisfying
Then, there exists an (n; K) code of minimum distance d over \Phi.
these values satisfy the equality
therefore, by Lemma 1 and Lemma 9 there exists a (2l; 2 rl ) code C
over F h
2 which is separable with respect to any subset of h2li of size l. Assign the coordinates
(over F h
of C to the nodes u 2 U 2l of G l and map the files w 2 F rl
into distinct codewords
of C. This protocol allows every node in G l to reconstruct any such file w, requiring a total
memory size of 2(r (compared to J(G l ; r \Delta
Remark 5. It can be readily verified that J(G m;l ; for every m, l, and
k, and, in particular, J(G l ;
. Hence, any file distribution protocol
for based on segmentation will be at least 1
times larger than the linear
programming bound ae G l \Delta k, even when k tends to infinity (see Example 1 and Remark 3).ffl
For file sizes k which are smaller than log \Delta G , one can find examples where the ratio
between M(G; J(G; k) is even larger than stated in Proposition 3. We demonstrate
this for the network graphs H l = G 2 l ;l in the next proposition, making use of the following
lemma.
Lemma 10. (The Plotkin bound [3, p. 315]). Let C be an (n; K) code of minimum
distance d over an alphabet of q elements. Then,q
Proposition 4.
l (k) stands for lim l!1 f l (k)=g l uniformly on k.
In particular, when l, the ratio M(H l ; k)=J(H l ; approximately l which, in turn,
is at least
log 2 \Delta H l .
Proof. We distinguish between the three ranges of k stated in the proposition.
Case 1: l. By (27) we have J(H l ;
l . In
fact, we also have M(H l ; l, we can construct a
Reed-Solomon code C RS over GF (2 r ), which is separable with respect to any subset of h2 l i
of size l [12, Chs. 10-11] (compare with Section 3.3). Assign the coordinates, over GF (2 r ),
of C RS to the nodes u 2 U 2 l of H l and map the files w
into distinct codewords of C RS .
By the separability of C RS every node in H l can readily reconstruct any file w
.
Case 2: strictly positive integer r ! l. Let x be the memory allocation
of a file distribution protocol for (H l ; of memory size Again, we assume
that x ;l and that the nodes in U 2 l are renamed to have x 1 - x 2 - x 2 l.
x
l
(compare with (28)).
To bound h from below, we regard the set
as an (n; 2 k ) code over an alphabet of q \Delta
separable with respect to
any subset of hni of size l, its minimum distance must be, by Lemma 1, at least
This, in turn, implies by Lemma 10 the inequality2 h
or,
Combining the last inequality with (29) yields
l
where o(1) stands for an expression, independent of k, which tends to zero as l goes to
infinity. Recalling that J(H l ;
r
The bounds (31) and (32) are definitive up to a multiplying factor of 1 \Gamma o(1): An upper
bound M(H l ; l is obtained by assigning the coordinates of a
Reed-Solomon code over GF (2 l ) to the nodes u 2 U 2 l of H l ; such a code is separable with
respect to any subset of h2 l i of size r and, therefore, with respect to any subset of size l.
Case 3: k ! l. Let n and h be defined as in case 2. Noting that (29) and (30) still apply,
we
l 2
i.e.,
le
l
Combining the last inequality with (29) yields
Turning to J(H l ; k), for k ! l we have J(H l ; (and, by Remark 5 we have,
in fact, equality): it is easy to verify that the integer vector
which is defined
by
y
satisfies the inequality AH l
1. Hence, by (33) we obtain
Again, the bounds (33) and (34) are definitive as we can simply replicate the file w into
each node u 2 U 2 l of H l , requiring a memory size of k \Delta 2 l .

Acknowledgment

We thank Noga Alon and Cynthia Dwork for the many helpful discussions and the anonymous
referee for the useful comments and the suggestion that we consider other variations on the
memory cost measure.


Appendix


The proofs of Propositions 1 and 2 make use of the following lemma.
Lemma 11. Let a = [a u real vectors in [0; 1] jV j and let
[Y u ] u2V be a vector of independent random variables over f0; 1g with Prob fY
Then,
(a) for every
a
e \Gammaffi
(b) for every
a
Proof. Lemma 11 is proved in [15] and [16]. Part (b) of the lemma appears as is in [15]
and for the sake of completeness we include the proof of part (a) here.
For a real random variable Z and constants fl - 0 and b, we have
e fl(b\GammaZ)
an inequality known as the Chernoff bound. Letting
for every fl - 0,
a
e \Gammafl auYu
Y
e \Gammafl auYu
Y
Substituting
a
where
Y
Y
exp f\Gammap u
Now, for a u 2 [0; 1] and t 2 (0; 1] we have Therefore,
a
which, for
e \Gammaffi
Part (a) is now obtained by substituting
Proof of Proposition 1. Let r denote the difference
Note that a \Delta z - 1 implies - a \Delta p and that a \Delta p - ' \Delta a \Delta z implies - '. Also, let Y be
the random variable as in (7). Then,
a
a
a
a
which readily proves the proposition for r - . Hence, we assume from now on that 0 - r !
- .
Apply Lemma 11(a) with - as in (36) and with
a
e \Gammaffi
oe
Therefore, to have Prob
a
it suffices to require that
oe
Case 1: r - 2oe. It is easy to verify that log e (1 2.
Hence, Inequality (37) is implied by
r
oe
- log e fi
which, in turn, is satisfied if r -
6 oe log e fi. Recalling that
Inequality (37) is thus implied by
Case 2: r ? 2oe. In this range,
oe \Delta log e
oe
oe
Hence, Inequality (37) is satisfied if
r - log e fi
The existence of the constant c 1 is now implied by (38) and (39) (setting c
Proof of Proposition 2. Let Y be the random variable as in (7) and let r be a positive
a
a
a
Now, the proposition holds trivially when a since, in this case, Prob
a
1.
Therefore, we assume from now on that a
Apply Lemma 11(b) with
a
Therefore, to have Prob
a
a
it suffices to require that
Case 1: r=(a
. Noting that (1
Inequality (40) is satisfied whenever
which, with E
a
- a \Delta p, is implied by
r
a
Case 2: r=(a \Delta
. Noting that t 7! (1+t \Gamma1 ) log e (1+t) is monotonously increasing
ii 5
3 log e2
i.e., Inequality (40) is satisfied if
The existence of the constant c 2 (such as c now implied by (41) and (42).



--R

A parallel algorithmic version of the Local Lemma
An algorithmic approach to the Lov'asz Local Lemma
Algebraic Coding Theory
Comparative models of the file assignment problem

Computers and Intractability: A Guide to the Theory of NP-Completeness
On the fractional solution to the set covering problem
File distribution problem for processor networks
A new polynomial-time algorithm for linear programming
On secret sharing systems
On the ratio of optimal integral and fractional covers
The Theory of Error-Correcting Codes
Optimal allocation of resources in distributed information networks
Efficient dispersal of information for security
Probabilistic construction of deterministic algorithms: approximating packing integer programs
Lecture notes on randomized algorithms
a technique for provably good algorithms and algorithmic proofs
How to share a secret
Ten Lectures on the Probabilistic Method
--TR

--CTR
Anxiao (Andrew) Jiang , Jehoshua Bruck, Network file storage with graceful performance degradation, ACM Transactions on Storage (TOS), v.1 n.2, p.171-189, May 2005
Stavros G. Kolliopoulos , Neal E. Young, Approximation algorithms for covering/packing integer programs, Journal of Computer and System Sciences, v.71 n.4, p.495-505, November 2005
Aravind Srinivasan , Chung-Piaw Teo, A constant-factor approximation algorithm for packet routing, and balancing local vs. global criteria, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.636-643, May 04-06, 1997, El Paso, Texas, United States
resource sharing;distributed networks;integer programming;linear programming;derandomization;set cover;linear codes;file assignment;probabilistic algorithms