arXiv:1706.03436v2 [cs.IT] 9 Jan 2018

Repair of Multiple Descriptions on Distributed
Storage
Anders Høst-Madsen

Heechoel Yang, Minchul Kim, Jungwoo Lee

Department of Electrical Engineering
University of Hawaii, Manoa
Honolulu, HI, 96822, Email: ahm@hawaii.edu

Department of Electrical and Computer Engineering
Seoul National University
E-mail: {hee2070,kmc1222}@cml.snu.ac.kr, junglee@snu.ac.kr

Abstract—In multiple descriptions on distributed storage, a
source is stored in a shared fashion on multiple servers. When a
subset of servers are contacted, the source should be estimated
with a certain maximum distortion depending on the number of
servers. The problem considered in this paper is how to restore
the system operation when one of the servers fail and a new
server replaces it, that is, repair. The requirement is that the
distortions in the restored system should be no more than in
the original system. The question is how many extra bits are
needed for repair. We find the optimum solution for a two server
problem in the Gaussian case, and an achievable rate for general
n nodes. One conclusion is that it is necessary to design the
multiple description codes with repair in mind; just using an
existing multiple description code results in unnecessary high
repair rates.

I. I NTRODUCTION
In distributed storage systems [1] information is stored
in a shared fashion among multiple servers; to recover the
information, in principle all servers are contacted and the
information combined. Multiple description coding [2] can be
seen as a variation of distributed storage. When only some
servers are contacted, instead of a failure, a distorted version
of the information is recovered. As more servers are contacted,
the distortion can be reduced. This can for example be used
for distributed storage of video.
A central issue in distributed storage is how to repair the
system when one or more of the servers fail or become
unavailable [1] and is replaced by new servers. In traditional
distributed storage this is in principle easily solved by using
minimum distance separable (MDS) (n, k) erasure codes:
when k out of n servers are available, the total information
can be recovered, and a new (n, k) erasure code generated.
With multiple description coding this is not a feasible solution:
when less than k servers are available with an (n, k) erasure
code, no information can be recovered, even with distortion –
as also explained in [3].
This leads us to the problem we consider in this paper.
A multiple description coding system is specified as follows:
when a subset S ⊂ {1, . . . , n} of servers are contacted, a
source X should be restored with a distortion at most D(S).
Now, if one (or multiple) of the servers fail, we should be able
to set up a replacement server with enough information so that
the whole region D(S), S ⊂ {1, . . . , n} is restored. There are
a number of variations of this problem

1) There is special (highly reliable) repair server that does
not participate in the usual operation of the system, but
only comes into action if another server fails. Either
a) The repair server can contact all other (non-failed)
servers and use their information combined with
its own information to restore the failed server
(collaborative repair).
b) The repair server has to restore the failed server
without contacting other servers (non-collaborate
repair).
2) The repair information is stored in a distributed fashion
among the n servers. Now it is immediately clear that
D({1, . . . , n}) cannot be restored. We can therefore
consider two cases
a) No more than n − 1 servers are ever accessed for
normal operation, and the problem is to restore
D(S) for |S| ≤ n − 1.
b) We require restoring the total region D(S) for all
S. The only solution here is to modify the system
so that D(S) = D({1, . . . , n}) for all S with |S| =
n − 1. The technical solution is therefore exactly
the same as above. The only difference is how to
do the accounting.
The problem we set out to solve is to find the minimum
information that can be stored on the servers so that the above
constraints can be satisfied.
The problem of repair of multiple descriptions has been
considered in a number of previous papers. In [4] the authors
consider a problem like 1. above, but they do not give a single
letter description of rate regions. In [5] the authors consider
practical codes for repairing. In the current paper we aim to
provide single letter expression for achievable rate regions,
and in some cases the actual rate region.
In the following we use the term repair node for the special
repair server and operational nodes to denote the other servers.
We use Ik = {1, . . . , k}, which used as an index means XIk =
[X1 , . . . , Xk ].
II. P ROBLEM D ESCRIPTION
We consider a symmetric multiple description problem as
in [6], and use their notation. We have an i.i.d. (independent identically distributed) source X that takes values in a

finite alphabet X and needs to be restored in the alphabet
X̂ , with generalizations to a Gaussian source through usual
quantization arguments [7]. We will first define the distributed
repair problem. For a source sequence xl of length l each
node stores lRt bits. For many achievable schemes, these
can be split into lR bits for normal operation and lRr
additional bits used only for repair. There are n encoding
functions fi : X l → {1, . . . , 2lRt } , 2n−1 decoding function
gJ : {1, . . . , 2lRt }|J| → X̂ l , J ⊂ In , and n repair functions
hi : {1, . . . , 2lRt }n−1 → {1, . . . , 2nRt }. We define the error
probability of repair as

Pr(l) = max P hi (fIn −{i} (xl )) 6= fi (xl )
i=1,...,n

We now say that a a tuple (Rt , D1 , . . . , Dn−1 ) is achievable
if there exists a sequence of (2lRt , l) codes with
lim max E[d|J| (xl , gJ (fJ (xl )))] ≤ Dm

l→∞ J:|J|=m

lim Pr(l) = 0

l→∞

(1)

the
distortions
d|J| (xl , x̂l )
=
˜
˜
d
(x
,
x̂
),
d
(x
,
x̂
)
≥
0.
We
call
this
exact
i
i
i
i
|J|
i=1 |J|
l
repair. The repaired node is required to be an exact copy of
the failed node, except that we allow a certain, vanishing,
error rate. Notice that the randomness in the system is purely
due to the source xl . Thus, for a given sequence xl either all
failures can be repaired exactly, and if they can be repaired
once, they can be repaired infinitely many times; or, some
failures can never be repaired. The probability of the source
sequences that are not repairable should be vanishing small.
An alternative problem formulation, which we call functional repair, is to allow approximate repair, where the only
requirement is that after repair the distortion constraint is
satisfied. In that case one would have to carefully consider
repeated repair. In this paper we will only consider strong
repair.
For a dedicated repair node, each node stores lR bits and
the repair node lRr bits. The non-collaborative repair functions
are instead functions hi : {1, . . . , 2lRr } → {1, . . . , 2lR }, and
the collaborative repair functions are hi : {1, . . . , 2lRr } ×
{1, . . . , 2lR }n−1 → {1, . . . , 2lR }, with the other definitions
similar.
with
Pl
1

III. T WO N ODES
We at first consider a problem with n = 2 nodes as this
is one of the only cases where the optimum rate distortion
region is known, in the Gaussian case [2] with mean-squared
distortion. If there is no repair node, the problem is trivial:
each node has to be able to achieve the distortion D2 by itself,
and they can therefore be copies of each other. We therefore
assume that there is a special repair node, and consider
the case when this has access to the surviving operational
nodes for repair, collaborative repair. The question is: what
is the minimum information the repair node can store, so that
(D1 , D2 ) can be achieved without any increase in storage rate
of the operational nodes.

The problem is most well posed in the Gaussian case, as
we know the exact rate distortion region (R, D1 , D2 ). We
then want to find the minimum repair rate Rr for every point
on the boundary of the rate distortion region (R, D1 , D2 ).
We also know that the El-Gamal Cover (EC) coding scheme
achieves the optimum rate-distortion region. The idea in the
EC scheme is that each node stores an index for use when only
that node is accessed, in addition to half the bits of an index
with refinement information that is only used when both nodes
are accessed. However, EC is clearly sub-optimum for repair.
Consider the point D2 = D1 ; in this point it is clear what is
the optimum solution. Each node has to be able to restore the
source by itself with distortion D2 , and they can therefore be
copies of each other. Repair then is done simply by copying
from the surviving node and Rr = 0. Now if D2 is close to
D1 one would expect Rr to be small. On the other hand, in
EC the two nodes store independently generated codewords –
even if the joint distribution is not independent [2]. Therefore
to restore the EC code exactly, Rr = 2R is needed.
We therefore instead consider the Zhang-Berger (ZB)
scheme [8], [7]. In addition to the individual and refinement
information stored in the EC scheme, the nodes in the ZB
scheme store a common codeword. While this cannot decrease
rate in the Gaussian case, a common codeword is great for
repair, as it can be simply copied from the surviving node
without additional information from the repair node.
Instead of the original characterization of the ZB scheme,
we will describe it in the language of PRP [6], both to be
consistent with the general problem later, and because the PRP
more explicitly characterizes the information stored on nodes
in terms of auxiliary random variable, which is essential to
calculate repair rate.
Theorem 1 (Zhang-Berger). A rate R is achievable if
1
R > I(X; U1 ) + H(Y12 |U1 ) + H(Y2 |Y12 , Y11 , U1 )
2
1
1
− H(Y12 , Y11 |X, U1 ) − H(Y2 |Y12 , Y11 , X, U1 )
2
2
for some conditional pdf p(u1 , y11 , y12 , y2 |x) such that
E[d1 (X, g1i (U1 , Y1i ))] ≤ D1 , E[d2 (X, g2 (U1 , Y1i ))] ≤ D2 .
Corollary 2. A repair rate Rr is achievable if
1
Rr > H(Y12 |Y11 , U1 ) − H(Y12 , Y11 |X, U1 )
2
1
1
+ H(Y2 |Y12 , Y11 , U1 ) − H(Y2 |Y12 , Y11 , X, U1 ) (2)
2
2
We omit the proof, as it is a special case of Theorem
6 later., but we will briefly outline how the repair works.
First, the common codeword needs no extra information for
repair. For the base layer, there are about l(H(Y12 |U1 ) −
1
2 H(Y12 , Y11 |X, U1 )) bits stored on each node. Suppose it
is known in advance that node 2 will fail. The repair
node could simply store a copy of the l(H(Y12 |U1 ) −
1
2 H(Y12 , Y11 |X, U1 )) bits of node 2. But at the time of
repair, the codeword in node 1 is known. We can use
that to reduce the number of required bits for repair to

l(H(Y12 |Y11 , U1 )− 12 H(Y12 , Y11 |X, U1 )) (the proof will make
more clear how this works). This gives the first term in
(2). It is of course not known in advance which node will
fail, but this can be solved through binning (think an (2, 1)
erasure code) without extra rate. The resolution information
requires about l(H(Y2 |Y12 , Y11 , U1 ) − H(Y2 |Y12 , Y11 , X, U1 ))
bits. Each operational node stores half the bits. The repair
node can then for example store the xor of the two sequences
of bits, so that the lost sequence can be recovered when the
other sequence is known; this gives the second term of (2).
It turns out the ZB is exactly optimum in the Gaussian case
Theorem 3. Consider a Gaussian source with E[X 2 ] = 1.
ZB achieves the following repair rate

 
1

log D12
D2 ≤ 2D1 − 1

4


 √


2
(1−D
)(D
−D
)
1
1
2
D1
√
2D1 − 1 ≤ D2 ≤ 2−D
Rr = 12 log
(D2 −1) D2
1





1
D1
D1

2 log D2
2−D1 ≤ D2
This is the optimum repair rate.
Proof: For achievable rate we let U1 = X + Qu1 , Y1i =
X + Q1i , Y2 = X + Q2 with Q... zero-mean Gaussian,
2
2
2
E[Q2u1 ] = σu1
, E[Q21i ] = σq1
, E[Q22 ] = σq2
, E[Q11 Q12 ] =
2
ρ1 σq1 , and all other noise variables uncorrelated. We first
calculate the distortions,
D1 =
D2 =

2 2
σq1
σu1
2 σ2 + σ2 + σ2
σq1
u1
q1
u1
2 2 2
(ρ1 + 1)σq1
σq2 σu1

(3)


2 σ2 σ2 + σ2 + σ2
2 2
(ρ1 + 1)σq1
q2 u1
q2
u1 + 2σq2 σu1

The D1 distortion constraint is always satisfied with equality,
and therefore
2
σq1
=

2
D1 σu1
2 − D σ2 − D
σu1
1 u1
1

(4)

Using standard Gaussian calculations of differential entropy,
we get


1
1
1
+ log
R = log 1 + 2
2
σu1
2

2
σu1

!

be achieved without transmitting resolution information, i.e.,
2
= ∞. From (??) we get
σq2
!
1
1
p
(7)
R = log
2
D1 1 − ρ21
2
independent of σu1
. This region is again split
into two. If
 
D1
D2 > 2−D1 we can achieve R = 21 log D11 , which is
achieved (and only achieved) for ρ1 = 0. What happens in
this region is that the two nodes have independent messages,
and the combination results in a distortion less than D2 . But
independent messages are poor for repair. We cannot change
ρ1 because of (7), but we can use the common message in the
2
ZB scheme. We choose the power σu1
so that the combination
of the two nodes’ information gives exactly a distortion D2 ,
D1 D2
2
. This solution is valid for
which gives σu1
= 2D2 −D
1 D2 −D1
D1
D2 > 2−D1 . We then get from (6) that


1
D1
Rr = log
2
D2
D1
we need to decrease ρ1 from zero.
For the case D2 ≤ 2−D
1
We store no common message. Then, solving (3) with respect
D2 +D1 −2D2
2
2
to ρ1 (for σq2
= ∞ and σu1
= ∞ ) gives ρ1 = D1 D
1 (D2 −1)
and
!
1
D2 − 1
p
R = log
2
2 (D1 − 1)D2 (D2 − D1 )
!
p
2 (D1 − 1)(D2 − D1 )
1
√
Rr = log
2
(D2 − 1) D2

In the region D2 ≤ 2D1 − 1 the optimum solution requires
storage of resolution information; we use no common message.
We get
s
!
1
1
R = log
2
D1 D2 (1 − ρ1 )(D1 (ρ1 − 1) + 2)
We minimize this with respect to ρ1 and get ρ1 =
Inserting this we get


1
1
√
R = Rr = log
2
D2

D1 −1
D1 .

p
2 + 1)
1 − ρ21 D1 (σu1
!


For the converse, we can think of the problem as follows.
2
2
2
2 2
D1 (ρ1 −1)σq2
σu1
+1 +(ρ1 +1)σu1
+2σq2
σu1
1
When the repair node has restored the failing operational
+ log
2 (D (ρ −1) (σ 2 +1)+2σ 2 )
4
σq2
1 1
u1
u1
node, the two operational nodes should be able to estimate
(5) X with a distortion1 (less than or equal to) D2 . But that
also means that the surviving node and the repair node when
and
they cooperate must be able to estimate X with a distortion
!
D2 . From standard
theory we then must have
 rate-distortion

1 − ρ1
1
1
2 2
Rr = log p
+ log 2σq2
σu1
1
1
log
.
Now
it
is
easy
to see that in all three
R
+
R
≥
2
2
2
r
2
2
2
D2
1 − ρ1 σq2 σu1
 


1
1
2
2
2
D1 (ρ1 − 1)σq2
σu1
+ 1 + (ρ1 + 1)σu1
(6) regions above, we have R + Rr = 2 log D2 .
Following [7, Theorem 13.2], there are three regions for
D2 to consider. If D2 ≥ 2D1 − 1, the optimum solution can

1 Notice that this is a much weaker requirement than (1) and corresponds
more or less to functional repair in Section II.

IV. G ENERAL n NODES

and using at most (n − 1) nodes for reconstruction
R ≥ H(Y1n ) +

For more than two nodes the optimum rate distortion region
is not known, not even in the Gaussian case. There are therefore many different schemes for multiple description coding,
e.g., [9], [10], [11], [6], and we have to design repair for
each specific method. In this paper we will consider the PRP
scheme [3], [6], as this is specifically aimed at the symmetric
case and is well-suited to repair. While there are certain cases
where the PRP scheme can be improved [10], these schemes
are much more involved and do not universally improve rate.
Let us briefly outline the standard PRP scheme. In layer k,
n codewords YkIn
To simplify the discussion, consider n = 3 nodes. The
problem is specified by the distortions (D1 , D2 ). As in the
two node case, there is one point where we know the optimum
solution: if D2 = D1 the optimum solution is to let all
three nodesbe identical copies, so that R = 12 log D1−1 =
−1
1
. The solution is continuous in this point: if D2 =
2 log D2
D1 − , we can store identical codewords in the tree nodes, in
this case so that each can individually restore to D2 , with a
rate R = 21 log D2−1 . There is no claim that this is optimum,
but it is better than the PRP solution: For D2 = D1 − the PRP
solution is to store completely independent codewords in the
three nodes (p(y11 , y12 , y13 |x) = p(y11 |x)p(y12 |x)p(y13 |x));
when they are combined the achieve less than D2 distortion.
Independent codewords are poor for repair, since independent redundant copies must be stored. One can improve
repairability by choosing correlated codewords Y11 , Y12 , Y13 ,
but not much. The issue is that the codebooks C1i of size
0
2lR for Y1i in [6, Section III.D] are generated independently
according to the marginal distribution p(y11 ). At encoding,
the encoder finds n codewords that are jointly typical with
xl . If the joint distribution is highly dependent, there are not
many such
Pn codewords: according to [3, (11)] we must have
nR0 > i=1 H(Yi ) − H(Y1 , . . . , Yn |X); if the Yi are highly
dependent (good for repair), the difference is large. This is
not specific to PRP, it is a common feature of all multiple
description coding schemes.
A solution is to allow common messages, as in ZB and
other schemes [9], [11]. This can seems like a crude solution,
but we know that this was exactly optimum in the two node
case. We are not claiming that this will improve PRP as such,
although it could, but it will improve repairability.
As baseline, consider the standard PRP scheme where we
use at most n − 1 nodes for the reconstruction. Now in layer
n−1, we just need a single common message (in standard PRP
that happens at layer n). This message can be encoded using
an (n, n − 1) MDS erasure code. We then get the following
rate which we state without proof as it is a simple modification
of PRP
Proposition 4. The following rate is achievable with n nodes

n−2
X
k=2

1
H(YkIk |YIk−1 ,Ik )
k

1
1
H(Yn−1 |YIn−2 In−1 ) − H(YIn−2 In |X)
+
n−1
n
1
−
H(Yn−1 |YIn−2 In−1 , X)
n−1
Repair is done layer-by-layer. In each layer, in addition
to the standard PRP codewords, we allow for a common
codeword shared among all nodes, and encoded with an (n, k)
erasure code, since a common codeword is good for repair, as
seen in the two node case. We now have the main result
Theorem 5 (Distributed repair). For any symmetric
probability distribution [6] p(yIn−2 ,In , uIn−2 , yn−1 |x)
and decoding functions gJ the lower convex closure
of (R + Rr , D1 , . . . , Dn−1 ) is achievable, where
E[d|J| (X, gJ (YI|J| J , UI|J| )] ≤ D|J| , |J| ≤ n − 1 and
the information needed to encode operational information is
R > I(X; U1 ) + H(Y1n |U1 ) +

n−2
X
k=2

1
H(YkIk |YIk−1 ,Ik UIk )
k

1
I(Yn−1 ; X|YIn−2 In−1 , UIn−2 )
+
n−1
1
− H(YIn−2 In |X, UIn−2 )
n
n−2
X1
(H(Uk |YIk−1 Ik , UIk−1 ) − H(Uk |X, YIk−1 In , UIk−1 )
+
k
k=1

with additional information needed to encode repair information
n−2 
1 X
H(Ykn |UIk , YkIn−1 YIk−1 In )
Rr >
n−1
k=1
+
1
− H(YkIn |X, Yk−1In , UIk )
n
with [x]+ = max{0, x}
Proof: Here we will just outline how the coding changes
compared to [3], [6], and reading the proof therefore requires
familiarity with those two papers; the journal version will
contain a formal proof. The formal proof is in the Appendix.
Consider first layer 1. We generate a random codebook Cu1
0
with 2lRu1 elements according to the marginal distribution
pU1 (u1 ). We also generate n independent random codebooks
0
C1In according to the distribution pY11 (y11 ) with 2lR1 codewords. We first look for a codeword in Cu1 that is jointly
typical with xl . Such a codeword can be found with high
probability if
0
Ru1 = Ru1
> H(U1 ) − H(U1 |X) = I(X; U1 )

This codeword is stored in all the nodes. Next we look for an
n-tuple of codewords from C1In that are jointly typical with xl

and the chosen codeword from Cu1 . These can be found with
high probability if (compare [3, (11)])
nR10 >

n
X

H(Y1i ) − H(Y11 , . . . , Y1n |U1 , X)

It next looks in the k bins for Yk1 , . . . , Ykk for codewords that
are jointly typical with (UIk , YIk−1 Ik ). With high probability
there is only one such is (compare [6, (15)])

(8)

k(Rk0 − Rk ) < kH(Yk1 ) − H(YkIk |UIk , YIk−1 Ik )

i=1

The codewords for each Y1j are binned into 2nR1 bins. At the
time of decoding, the codeword for U1 is available as well as
the bin number i for Y1j . The decoder looks for a codeword
in bin i that is typical with U1 . If there is more than one, the
decoding results in error. If (compare [3, (12)])
R10 − R1 < H(Y11 ) − H(Y11 |U1 )

(9)

there is only one such codeword with high probability. Combining (8) and (9) we get

or
1
1
H(YkIk |UIk , YIk−1 Ik )− H(YkIn |X, UIk , YIk−1 In )
k
n
(as in [3] this can be repeated for any collection of k nodes).
At layer n − 1 only a single codebook is generated, and
this is binned into n independent partitions. Upon receipt,
in analogy with (10), this can be found uniquely with high
probability if
Rk >

1
H(Yn−1 |YIn−2 In−1 , UIn−2 )
n−1
1
−
H(Yn−1 |X, YIn−2 In , UIn−2 )
n−1

Rn−1 >

R1 > H(Y11 |U1 ) − H(Yi1 , . . . , Yin |U1 , X)
At layer k < n−1 we similarly generate a random codebook
0
Cuk with 2lRuk elements according to the marginal distribution
pUk (uk ) and n independent random codebooks CkIn according
0
to the distribution pYk1 (yk1 ) with 2lRk codewords. We first
look for a codeword in Cuk that is jointly typical with xl
and all the codewords chosen in the previous layers. This is
possible with high probability if (compare [6, (12)]
0
Ruk
> H(Uk ) − H(Uk |X, YIk−1 In , UIk−1 )

we then choose an n-tuple of codewords from CkIn that are
jointly typical with all prior codewords and xl , which is
possible with high probability if (compare [6, (12)]
nRk0 >

n
X

H(Yki ) − H(YkIn |X, Yk−1In , UIk )

i=1

For Uk we generate n independent binning partitions each
with 2lRuk elements. The bin number in the i-th partition is
stored in the i-th node2 . The codewords for each of the Ykj
are binned into 2lRk bins, and the bin number for Ykj stored
in node j.
At the decoder, k random nodes are used – due to symmetry
we can assume these are the first k nodes. We assume that the
decoding of the previous layers have been successful. So we
know correctly the codewords for U1 , . . . , Uk−1 , as well as
YIk−1 Ik , and k bin numbers for Uk the bin number for each
of Yk1 , . . . , Ykk .
The decoder first looks for a common codeword in the k
bins for Uk that is jointly typical with (UIk−1 , YIk−1 Ik ). With
high probability there is only one such if (compare [3, Section
III.E])

0

For repair, the joint 2nlRk codewords in Ck1 × · · · × Ckn
at layer k < n − 1 are binned into 2lRrk bins. The single
bin number of the n chosen codewords is encoded with an
(n, n − 1) MDS erasure code.
Now suppose node n is lost, and needs to be recovered. The
repair works from the bottom up. So, suppose the bottom k−1
layers have been recovered, that is, YIk−1 Ib , UIk−1 are known
without error. First Uk is recovered, which can be done since
n − 1 ≥ k nodes are used. It can also decode the codewords
corresponding to YkIn−1 . It restores the bin number of the
joint codeword from the erasure code. There are approximately
0
2l(nRk −Rrk ) codewords in the bin, but since it knows the
0
codewords of YkIn−1 there are only about 2l(Rk −Rrk ) valid
ones. It searches in this bin for codewords jointly typical with
YkIn−1 YIk−1 In , UIk . With high probability there is only one
such if
Rk0 − Rrk < H(Ykn ) − H(Ykn |UIk , YkIn−1 YIk−1 In )
or

Rrk > H(Ykn |UIk , YkIn−1 YIk−1 In )
1
(11)
− H(YkIn |X, Yk−1In , UIk )
n
There is at least one codeword in the bin, namely the correct
one. Thus, if there is no error (more than one codeword),
the repair is exact, as required from the exact repairability
condition in Section II.
The above result can easily be adapted to the case of a repair
node that collaborates with the operational nodes. There are
0
only two differences
kRuk > Ruk
+ H(Uk |YIk−1 Ik , UIk−1 ) − H(Uk )
• The repair node can restore operation of the full n node
or
distortion region. Therefore, the terminal single common
1
codeword is not at layer n − 1 but at layer n. At the same
Ruk > (H(Uk |YIk−1 Ik , UIk−1 )−H(Uk |X, YIk−1 In , UIk−1 ))
k
time, the repair node now has to store repair information
(10)
for this last codeword.
• For distributed repair, distributions are chosen to mini2 As argued in [3, Section III.E] this kind of binning is equivalent to MDS
erasure codes.
mize R + Rr . For a repair node, distributions are chosen

to minimize R, and Rr is then as given for those
distributions.

1
R ≥ I(X; U1 ) + H(Y13 |U1 ) + H(Y2 |Y13 , Y12 , U1 )
2
With this in mind, we get
1
1
− H(Y13 , Y12 , Y11 |X, U1 ) − H(Y2 |Y13 , Y12 , X, U1 )
3
2
Theorem 6 (Collaborative repair node). For any symmetric
1
1
probability distribution p(yIn−1 ,In , uIn−1 , yn |x) and decoding Rr ≥ H(Y13 |Y12 , Y11 , U1 ) − H(Y13 , Y12 , Y11 |X, U1 )
2
6
functions gJ the lower convex closure of (R, D1 , . . . , Dn ) is
We
put
U
=
X
+
Q
,
Y
=
X + Q1i , Y2 = X + Q2 with
U1
1i
achievable, where E[d|J| (X, gJ (YI|J| J , UI|J| )] ≤ D|J| , |J| ≤
2
2
2
2
Q
zero-mean
Gaussian,
E[Q
...
n and
u1 ] = σu1 , E[Q1i ] = σq1 ,
2
2
2
E[Q2 ] = σq2 , E[Q1i Q1j ] = ρ1 σq1 , and all other noise
variables
uncorrelated. Space does not allow us to write down
n−1
X1
all details of the solution, but we will outline the structure.
R > I(X; U1 ) + H(Y1n |U1 ) +
H(YkIk |YIk−1 ,Ik UIk )
k
The distortion and rates are calculated as in the proof of
k=2
1
1
Theorem 3. As in that proof there are three solution regions:
+ H(Yn |YIn−1 In , UIn−1 ) − H(YIn−1 In |X, UIn−1 )
for small D2 the nodes store resolution information, but no
n
n
n−1
common information. For medium D2 the nodes store neither
X1
+
(H(Uk |YIk−1 Ik , UIk−1 ) − H(Uk |X, YIk−1 In , UIk−1 )) resolution information nor common information; distortion D2
k
k=1
is achieved solely through adjusting ρ1 . And for large D2 the
nodes store a common message, but no resolution information.
The additional information the repair node has to store is
In all three regions it is possible to obtain closed form
expressions of rates, but they must be numerically optimized
n−1
over ρ1 .
X
Rr >
H(Ykn |UIk , YkIn−1 YIk−1 In )
The distortions are still given by (3) and we still have (4).
k=1
Then
+


1
1
1
− H(YkIn |X, Yk−1In , UIk )
R = log 1 + 2
n
2
σu1
!
1
2
1
1
1 + σq1
− 1+σ
2
1
+ H(Yn |YIn−1 In , UIn−1 ) − H(YIn−1 In |X, UIn−1 )
u1
+ log
n
n
1/3 2
2
((ρ1 − 1)2 (2ρ1 + 1)) σq1
!
2
2 2
2
2
2 2
A. Example Gaussian case
(ρ1 + 1)σq1
(σq2
σu1 + σq2
+ σu1
) + 2σq2
σu1
1
+ log
2 (σ 2 + 1) + 2σ 2 )σ 2
4
((ρ1 + 1)σq1
u1
u1 q2
and

D1=0.2
2
2 nodes EC
3 nodes PRP
3 nodes modfied PRP
3 nodes with repair, no common message
3 nodes with repair, common message

1.9
1.8

Rr =

1.6
R+Rr

2
2
2
2
(1 − ρ1 )σq1
((2ρ1 + 1)σq1
(σu1
+ 1) + 3σu1
)

1/3 2
2 (σ 2 + 1) + 2σ 2
2
(ρ1 + 1)σq1
σq1
u1
u1 ((ρ1 − 1) (2ρ1 + 1))

Following the proof of Theorem 3 we first consider a
2
solution with no resolution information, i.e, σq2
= ∞. Then
we have
2
D1 (ρ1 + 1)σu1
D2 =
2 + 1) + 2σ 2
D1 (ρ1 − 1)(σu1
u1

1.7

1.5
1.4

And

1.3

1
R = log
2

1.2
1.1
1

1
log
4

0

0.02

0.04

0.06

0.08

0.1
D2

0.12

0.14

0.16

0.18

0.2

Figure 1. Plots of R or R + Rr for (a) two nodes according to [2] (b)
Three nodes with at most two used, without repair according to PRP [6] or
Theorem 5 (modified PRP) and (c) Three nodes with distributed repair without
or without common message.

We consider a three node Gaussian case with mean-squared
distortion and with distributed repair. This is characterized
by (R + Rr , D1 , D2 ). From Theorem 5 we get specifically
(omitting the []+ operation)

1
Rr = log
4

!

1
D1

p
3
(ρ1 − 1)2 (2ρ1 + 1)
2
2
(1 − ρ1 )(2D1 (ρ1 − 1)(σu1
+ 1) + 3σu1
)

p
3

2 + 1) + 2σ 2 )
(ρ1 − 1)2 (2ρ1 + 1)(D1 (r − 1)(σu1
u1

For the solution without common information we get3
r

2D1 (ρ1 −1)+3


1
Rt = log 

2
3 This

(−2ρ21 +ρ1 +1)(D1 (ρ1 −1)+2) 


D1

expression is only valid for such ρ1 that Rr > 0.

!

This can be numerically minimized over ρ1 ∈ (− 21 , 1). But
we also need the D2 constraint satisfied, which requires

D1 D2 (1 − ρ1 )
2D2 − D1 (D2 (1 − ρ1 ) + ρ1 + 1)

The proof is a modification of the proof of Theorem 2 in
[6], and we will therefore follow their steps closely. We let
Tl (X) denote the strongly  typical set for X.
The coding scheme for repair uses MDS erasure codes in
several places. These can be put in the binning framework of
PRP [3]. However, it is easier to think of them as pure channel
codes. We can state this as follows:

2D2 − D1 D2 − D1
D1 (1 − D2 )

Remark 7. A message M ∈ {1, . . . , 2lR } is stored on n
servers, of which at least k is accessed for decoding. With
R0 > k1 R bits on each server, decoding is possible with error
P (E) → 0 as l → ∞.

ρ1 ≤

D1 D2 + D1 − 2D2
D1 (D2 − 1)

Now, with common information, we aim to achieve exactly
D2 , so that
2
σu1
=

This is valid for
ρ1 <
Then

A. Codebook generation


Rt =

q

D2 −2D1 (ρ1 +1)
D1 (2ρ1 +1)



D2
1

log 
2
D1 ρ1 + D1 − 2D2

which must again by numerically optimized over ρ1 .
2
With resolution information we put σu1
= ∞ and
2
σq2
=

D1 D2 (ρ1 + 1)
D1 (D2 (−ρ1 ) + D2 + ρ1 + 1) − 2D2

This is valid if
ρ1 >
Then

A PPENDIX A
P ROOF OF T HEOREM 5

2D2 − D1 D2 − D1
D1 (1 − D2 )

q


D1 (ρ1 +1)
1
D2 (D1 (ρ1 −1)+2)

Rt = log  p
2
D1 3 (ρ1 − 1)2 (2ρ1 + 1)

Figure 1 shows typical numerical results. First, from the
bottom, we have the curve for the optimum region for the
two node problem according to EC [2], [7]. Notice that
this is achieved without any refinement information, using
only correlation between the base layer random variables;
refinement information is only required for D1 > 21 and
D2 < 2D1 − 1. Second, we have the curves for the three
node problem, but where we use at most two nodes for
reconstruction, either using [6, Section V] directly (ignoring
the D3 constraint), or using Theorem 5 without repair. It can
be noticed that using Proposition 5 gives a slight improvement;
this is not due to the common message, but due to the fact that
PRP uses n−1 codewords in the last layer, while the modified
PRP uses only one. Finally, we have the curves for repair. We
see that a common message gives a clear improvement.
V. C ONCLUSION
Our solutions show that it is sub-optimum for repair to
just take a standard multiple description code and add repair
information. Rather, the multiple description code has to be
designed with repair in mind. In this paper we do this by
adding common messages. For the two node case this was
shown to be optimum. However, for the n node case, there
might be better solutions.

The codebooks CIn−2 In are generated and binned exactly as
in [6]. The difference from [6] is that there is no n-th layer,
and that at layer n − 1 there is only one codebook Cn−1 . The
0
codebook Cn−1 of size 2lRn−1 is generated like Cn in [6], but
then stored on the nodes with an (n, n − 1) MDS code.
We also generate n −2 common codebooks 
CuIn−2 by
0
0
(l)
(l) lRu
lRuk
drawing 2
codewords uk (1), . . . , uk (2 k ) independently with replacement over the set Tl (Uk ) according to a
uniform distribution. The indices for Cuk , k = 2, . . . , , n − 2
0
are next binned. Let ξuk = 2l(Ruk −Ruk +γuk ) for some γk > 0
and make 2lRuk bins. For each bin, select ξuk numbers from
0
the set {1, . . . , 2lRuk }, uniformly and with replacement. They
are finally coded with an (n, k) MDS erasure code.
We finally generate (n − 1) repair codebooks through
binning. First, if
0 > H(Ykn |UIk , YkIn−1 YIk−1 In )
1
(12)
− H(YkIn |X, Yk−1In , UIk )
n
it turns out, as will be seen later, that the lost codeword can
be recovered from the remaining ones with high probability.
In that case we set Rrk = 0 and store no extra repair
information. For consistency we think of there being one bin
at layer k containing all codewords. Otherwise, we let ξrk =
0
2l(nRk −Rrk +γrk ) for some γrk > 0 and make 2lRrk bins.
0
For each bin, select ξrk vectors from the set {1, . . . , 2lRk }n ,
uniformly and with replacement. The bin indices are further
coded with an (n, n − 1) MDS erasure code.
B. Encoding
Given a source codeword x(l) ∈ X l we find codewords so
that


(l)
(l)
(l)
x(l) , uIn−2 (VIn−2 ), yIn−2 In . ∗ (QIn−2 Im ), yn−1 (Qn−1 )
are jointly typical. The binning of QIn−2 Im and Qn−1 are
done exactly as in [6] to obtain bin indices BIn−2 In , Bn−1 .
The bin index Bn−1 is further coded with the (n, n − 1) MDS
code. For Vk we find the smallest bin index Buk that contains
Vk (if Vk is in no bin, Buk = 0), and this is further coded
with the (n, k) MDS code.

For repair, for those k ∈ In−1 where repair information is
needed, we find the smallest bin index Wk so that QkIn is in
the corresponding bin; if no bin contains Wk we put Wk = 0.
These are then coded with the (n, n − 1) MDS code.
C. Decoding
We assume node 1, 2, . . . , j are available. The bin indices
BuIj0 are decoded from the MDS code, where j 0 = min{j, n−
2}. The decoding now is similar to [6], except that there is
also a common codeword. Consider decoding at layer k ∈
{2, . . . , j 0 }. First we find an index Vk in bin Buk so that



(l)
(l)
(l)
yIk−1 Ij , uk (Vk ), uIk−1 ∈ Tl YIk−1 Ij , UIk
Next, for any size k subset S ⊂ Ij the decoder looks in bins
(l)
BkS for codewords ykS so that



(l)
(l)
(l)
ykS , yIk−1 Ij , uIk ∈ Tl YkIk , YIk−1 Ij , UIk
If j = n − 1, Bn−1 is first recovered from the MDS code.
Then the above procedure is repeated (there is no Un−1 ).
The reconstructions of x̂(l) is standard as in [6].
D. Repair
Without loss of generality and to simplify notation, we can
assume that node n fails. The repair is done layer by layer. At
layer 1, we copy V1 from any node to the replacement node
n. Next, from the (n − 1) surviving nodes we decode the
repair bin index W1 from the MDS code; if there is no extra
repair information we put W1 = 1. We know Q1In−1 from
the surviving nodes. In bin W1 we look for an index Q1n so
(l)
that the corresponding codeword (y(l) . ∗ (Q1In ), u1 (V1 )) ∈
l
T (Y1In , U1 ) ; if there is more than one, there is a repair error.
We then store the recovered Q1n in the replacement node n.
The following layers proceed in almost the same way. But
now to recover the common messeage Vk we choose arbitrarily
k of the surviving nodes and decode Vk just as with usual
operation. The decoded Vk is then encoded with the exact
same MDS code and we store the corresponding codeword on
the replacement node n. We next find an index Qkn in bin
(l)
(l)
Wk so that (yIk In . ∗ (QIk In ), uIk (VIk )) ∈ Tl (YIk In , UIk ) .
On the last layer we simply decode Qn−1 from the surviving
nodes as usual, and then we re-encode with the same MDS
code, and store the recovered bin index on the new node n.
We notice that this repair is exact: the information on the
restored node is exactly the same as on the failed node, except
if a repair error happens.

2) E1 : There exists no indices so that

(l)
(l)
x(l) , uIn−2 (VIn−2 ), yIn−2 In . ∗ (QIn−2 Im ),

(l)
yn−1 (Qn−1 )
∈ Tl (X, UIn−2 , YIn−2 In , Yn−1 )
3) E2 : Not all the indices (B2In , . . . , B(n−2)In , Bn−1 ) are
greater than zero.
4) E3 : For some subset S ⊂ In with |S| = k ∈ {2, . . . , n−
2} there exists some other Q0kS in bins BkS so that4



(l)
(l)
(l)
ykS (Q0kS ), yIk−1 Ij , uIk ∈ Tl YkIk , YIk−1 Ik , UIk
5) E4 : not all the indices Buk are greater than zero.
6) E5 : For some 2 ≤ k ≤ n − 2 there exist another index
Vk0 6= Vk in bin Buk so that



(l)
(l)
(l)
yIk−1 Ij , uk (Vk0 ), uIk−1 ∈ Tl YIk−1 Ik , UIk (13)
7) E6 : There is a decoding error in the (n, k) MDS erasure
code for Buk .
8) E7 : There is a decoding error in the (n, n − 1) MDS
erasure code for Bn−1 .
First by Remark 7, P (E6 ), P (E7 ) → 0 as long as the rates
before the MDS is scaled appropriately.
As in [6] we have P (E0 ) → 0 as l → ∞. For E1 as in [6]
we define E1i as an encoding error on layer i given that the
previous layers have been encoded correctly and in addition,
(l)
here, that ui has been encoded correctly. Then as in [6] we
get that P (E1i ) → 0 if
nR10 > nH(Y11 ) − H(Y1In |X, U1 )
nRi0 > nH(Yi1 ) − H(YiIn |X, YIi−1 In , UIi−1 )
0
nRn−1
> I(Yn−1 ; X, YIn−2 In UIn−2 )

(14)

with the difference being the addition of the U∗ variables.
(l)
u
Similarly, we can define E1i
as an encoding error of ui given
that the previous layers have been encoded correctly, and we
u
similarly have that P (E1i
) → 0 if
0
Ru1
> H(U1 ) − H(U1 |X)
0
Rui
> H(Ui ) − H(Ui |X, YIi−1 In , UIi−1 )

(15)

The proof that P (E2 ) → 0 is unchanged from [6], and the
proof that P (E4 ) → 0 is similar.
The proof that P (E3 ) → 0 is similar to [6], except that at
(l)
the time of decoding at layer k the decoder has access to uIk .
The relevant probability of decoding error at layer k therefore
is P (E3k |Ec3Ik−1 , E2c , E4c , Ec5Ik , E6c , E7c ), and since we search

for codewords in Tl YkIk , YIk−1 Ij , UIk , the condition for this
error probability converging to zero is

E. Analysis of Decoding Error
We have some slightly modified error events compared to
[6] and some additional ones. We find it necessary to write
these down explicitly
1) E0 : x(l) ∈
/ Tl (X).

Rk > Rk0 − H(Yk1 ) +

1
H(YkIk |UIk , YIk−1 Ik )
k

(16)

4 We use a slightly different notation for E compared to [6], which we
3
think is clearer.

instead of [6, (A17)].
To prove that P (E5 ) → 0 we let E5k be the
decoding error on layer k, and then bound P5k =
P (E5k |Ec3Ik−1 , E2c , E4c , Ec5Ik−1 , E6c , E7c ). If we pick a random
(l)
uk

Tl (Uk )

codeword
∈
the probability that this is jointly
typical, i.e., the event (13), is
P ≤ 2−l(I(Uk ;YIk−1 UIk−1 )−δ())
0

There are ξuk = 2l(Ruk −Ruk +γuk ) elements in each bin, and
therefore,
P5k ≤ ξuk P
if we let γuk > δ() we have P5k → 0 if
0
Ruk
− Ruk < I(Uk ; YIk−1 UIk−1 )

Together with (15) this gives (10).
F. Analysis of Repair error
If E4−7 , from above happen, there is also a repair error.
Notice that at time of repair, we have access to n − 1 nodes,
and we can therefore use decoding
P7 for n − 1 nodes, and in
that case we have proven that i=4 P (Ei ) → 0 as l → ∞.
We have the following additional repair error events
1) Er1 : Some Wk = 0 for k ∈ In−2 .
2) Er2 : For k ∈ In−2 there exists another bin index Q0kn
in bin Wk so that
(l)

(l)

N

= −2lγrk → −∞ as l → ∞
2) Bounding Er2 : First we will argue that if (12) is satis(l)
fied, we can predict ykn with probability approaching one. We
(l)
can state this as follows: if we pick a random ykn ∈ Tl (Ykn ),
what is the probability P that
(l)

(l)

(ykn , ykIn−1 (QkIn−1 ), yIk−1 In . ∗ (QIk−1 In ), uIk (VIk ))
∈ Tl (YIk In , UIk )
(17)
This is actually a standard channel coding problem, so we get
P ≤ 2−l(I(Ykn ;YkIn−1 ,YiIn−1 ,UIk )−δ())
Since the codebook Cuk has 2

(18)

elements, we then have
0

P (Er2k ) ≤ 2lRk P

0

P (Er2k ) ≤ ξrk P2 P = 2l(Rk −Rrk +γrk ) P
if we choose γrk > δ() we have P (Er2k ) → 0 as l → ∞ if
Rk0 − Rrk < H(Ykn ) − H(Ykn |YkIn−1 , YiIn−1 , UIk )
Which together with (14) and the argument above leads to
(11).
[1] A. G. Dimakis, P. B. Godfrey, Y. Wu, M. J. Wainwright, and K. Ramchandran, “Network coding for distributed storage systems,” IEEE
Transactions on Information Theory, vol. 56, no. 9, pp. 4539–4551,
Sept 2010.
[2] A. E. Gamal and T. Cover, “Achievable rates for multiple descriptions,”
IEEE Transactions on Information Theory, vol. 28, no. 6, pp. 851–857,
Nov 1982.
[3] S. S. Pradhan, R. Puri, and K. Ramchandran, “n-channel symmetric
multiple descriptions - part I: (n, k) source-channel erasure codes,” IEEE
Transactions on Information Theory, vol. 50, no. 1, pp. 47–61, Jan 2004.
[4] T. H. Chan and S. W. Ho, “Robust multiple description coding ; joint
coding for source and storage,” in 2013 IEEE International Symposium
on Information Theory, July 2013, pp. 1809–1813.
[5] D. Kapetanovic, S. Chatzinotas, and B. Ottersten, “Index assignment
for multiple description repair in distributed storage systems,” in 2014
IEEE International Conference on Communications (ICC), June 2014,
pp. 3896–3901.
[6] R. Puri, S. S. Pradhan, and K. Ramchandran, “n-channel symmetric
multiple descriptions-part II:an achievable rate-distortion region,” IEEE
Transactions on Information Theory, vol. 51, no. 4, pp. 1377–1392,
April 2005.
[7] A. E. Gamal and Y.-H. Kim, Network Information Theory. Cambridge
University Press, 2011.
[8] Z. Zhang and T. Berger, “New results in binary multiple descriptions,”
IEEE Transactions on Information Theory, vol. 33, no. 4, pp. 502–521,
Jul 1987.
[9] R. Venkataramani, G. Kramer, and V. K. Goyal, “Multiple description
coding with many channels,” IEEE Transactions on Information Theory,
vol. 49, no. 9, pp. 2106–2114, Sept 2003.
[10] C. Tian and J. Chen, “New coding schemes for the symmetric k description problem,” IEEE Transactions on Information Theory, vol. 56,
no. 10, pp. 5344–5365, Oct 2010.
[11] K. B. Viswanatha, E. Akyol, and K. Rose, “Combinatorial message
sharing and a new achievable region for multiple descriptions,” IEEE
Transactions on Information Theory, vol. 62, no. 2, pp. 769–792, Feb
2016.

0

0
lRk

which is (12).
Now turn to the case when (12) is not satisfied. We look
0
for vectors (Q0k1 , Q0k2 , . . . , Q0kn ) ∈ {1, . . . , 2lRk }n that
1) Are in the bin indicated by Wk .
2) Has Q0ki = Qki , i ≤ n − 1.
3) Are jointly typical, i.e., satisfy (17).
For condition 3, (18) is still valid. Each bin contains ξrk =
0
2l(nRk −Rrk +γrk ) vectors. Each of these has probability P2 =
2−l(n−1)Rlk of satisfying conditions 2. Therefore

R EFERENCES

was never picked then is P (Er1 ) = 1 − 2−nlRrk
and


0
0
log P (Er1 ) = N log 1 − 2−nlRrk ≤ −N 2−nlRrk

(l)

Now in consideration of (16) there is no gain from making
Rk0 larger than needed. Thus Rk0 is chosen arbitrarily close to
the limit given by (14), and we therefore have P (Er2k ) → 0
if
1
H(Yk1 ) − H(YkIn |X, YIk−1 In , UIk−1 )
n
< H(Ykn ) − H(Ykn |YkIn−1 , YiIn−1 , UIk ) − δ()

Tl (YIk In , UIk )

3) Er3 : For k ∈ In−2 there is a decoding error in the
(n, n − 1) MDS erasure code for Wk .
1) Bounding Er1 : In total, for all bins, we pick N =
0
2lRrk ξrk = 2l(nRk +γrk ) elements with replacement from a
0
set of size 2nlRrk . The probability that
 a particular
 element

(l)

Rk0 < H(Ykn ) − H(Ykn |YkIn−1 , YiIn−1 , UIk ) − δ()

(l)

(ykIn (Q0kIn ), yIk−1 In . ∗ (QIk−1 In ), uIk (VIk ))
∈

Thus, P (Er2k ) → 0 as l → ∞ if

