1

Cooperative Data Exchange based on MDS Codes
Su Li and Michael Gastpar

arXiv:1712.02306v1 [] 6 Dec 2017

Abstract
The cooperative data exchange problem is studied for the fully connected network. In this problem, each node initially only
possesses a subset of the K packets making up the file. Nodes make broadcast transmissions that are received by all other nodes.
The goal is for each node to recover the full file. In this paper, we present a polynomial-time deterministic algorithm to compute
the optimal (i.e., minimal) number of required broadcast transmissions and to determine the precise transmissions to be made by
the nodes. A particular feature of our approach is that each of the K − d transmissions is a linear combination of exactly d + 1
packets, and we show how to optimally choose the value of d. We also show how the coefficients of these linear combinations
can be chosen by leveraging a connection to Maximum Distance Separable (MDS) codes. Moreover, we show that our method
can be used to solve cooperative data exchange problems with weighted cost as well as the so-called successive local omniscience
problem.
Index Terms
Cooperative data exchange, maximum distance separable codes, linear codes

I. I NTRODUCTION
Consider a fully connected network composed of N nodes that all want to recover a K packet file. Each node initially only
has a subset of the packets. Each node can generate coded packets by using its locally available packets and transmit them to
other nodes through a lossless broadcast channel, i.e. all other nodes receive the coded packets. The goal is for each node to
assemble the full file. The key questions are: (1) What is the minimum number of required transmissions? (2) What should
individual nodes transmit? This problem was introduced by El Rouayheb et al. in [1] and is referred to as Cooperative Data
Exchange (CDE) or communication for omniscience for the fully connected network. Concerning the minimum number of
required transmissions, upper and lower bounds were established in [1]. A deterministic algorithm was proposed to produce
a coding scheme which achieves universal recovery using at most twice the minimum number of required transmissions. The
CDE problem can be formulated as an Integer Linear Program (ILP) with the Slepian-Wolf constraints on all proper subsets
of the nodes’ available packet information. A randomized algorithm [2] and a deterministic algorithm [3] were proposed to
give an approximate solution and solve the problem with high probability. We note that the number of constraints in the ILP
at hand grows exponentially with the problem size. Nevertheless, exact polynomial-time algorithms were found in [4], [5], [6]
based on minimizing submodular functions and subgradient optimization.
A. Main Contributions
In this paper, we consider the CDE problem for the fully connected network in a new perspective. Our main contributions
can be summarized as follows:
(1) We present a new deterministic algorithm to compute the minimal number of required transmissions. It is based on
searching for the existence of certain conditional bases of the packet distribution matrix. The complexity is bounded by
O(N 3 K 3 log(K)), significantly lower than the complexity of the best known existing algorithms proposed in [4] based
on minimizing submodular functions O((N 6 K 3 + N 7 ) log(K)) and based on subgradient methods O((N 4 log(N ) +
N 4 K 3 )K 2 log(K)).
(2) We propose a novel coding scheme with K − d transmissions in which each transmission is a linear combination of d + 1
packets for any 0 ≤ d < K. Nodes with at least d packets can recover their missing packets from this coding scheme
regardless of which packets they have in detail. The coefficient matrix of the coding scheme can be efficiently generated
by performing elementary row operations on Vandermonde matrices.
(3) We show that the CDE problem with weighted cost objective function and successive local omniscience problem can
be solved by our method with slightly modifications. The complexity of our method for solving CDE problem with
weighted cost objective function is bounded by O(N 3 K 3 log(K)), which is the same as CDE problem without weighted
cost. For successive local omniscience problem with M priority groups, our methods has complexity bounded by
O(N 3 K 3 M log(K)). For both generalized problem, the way of constructing coding scheme is the same as what we
do for basic CDE problem.
This paper was partially presented at the 2017 IEEE International Symposium on Information Theory, June, and at the 2017 55th Annual Allerton Conference
on Communication, Control, and Computing, October.

2

B. Further Related Work
The CDE problem was extended to general network topologies, and it was shown that linear codes are sufficient to optimally
solve the CDE problem in [5], [7]. However, the same work also revealed that for arbitrarily connected networks, the CDE
problem is NP-hard and cannot be solved exactly with polynomial time algorithms. Many extensions of the CDE problem
have also been studied. In [8], the nodes are divided into two classes, high and low priority. The resulting CDE problem
with priorities was formulated as a multi-objective integer linear program. Assuming a uniformly random packet distribution
and restricting to the limit as the number of packets tends to infinity, a closed-form expression for the minimal number of
required transmissions was derived. In [4], [9], transmissions sent by different node are considered to have different cost.
Instead of minimizing the total number of transmissions, the goal becomes minimizing the total cost, i.e., a weighted sum of
the transmissions. To solve the CDE problem with weighted cost, a deterministic polynomial algorithm based on submodular
function minimization was proposed in [4], while a randomized greedy algorithm was proposed in [9]. In [5], [10], it is
assumed that each packet can be split into the same number of smaller chunks and the optimization goal is minimizing the
normalized total number of transmissions. Intuitively, the larger the number of chunks we split each packet into, the smaller
the normalized total number of transmissions that can be achieved, and it has been proved that it is sufficient to split each
packet into N − 1 chunks. In [11], the nodes are divided into two classes, reliable and unreliable. For unreliable nodes, the
initially available packets are unknown (but it is known how many packets they have) and the packet transmissions are subject
to arbitrary erasures. A closed-form expression for the minimal number of transmissions for the case of only a single unreliable
node was derived with probability approaching 1 as the number of packets tends to infinity. For more than one unreliable node,
an approximate solution was provided.
The CDE problem for the fully connected network is also related to the secret key generation problem, which was introduced
in [12] and was formulated as a maximization problem over all partitions of the node set. Tyagi et al. [13] leveraged this to
derive an algorithm which achieves local omniscience in each step and outputs a sub-optimal solution. The weakly secure data
exchange problem was introduced in [14]. The goal is to achieve universal recovery while revealing as little information as
possible. In contrast to the coding scheme in [14] in which each transmission is a linear combination of as many packet as
possible, our scheme considers a fixed number of packets for every transmission. In general cases, the communication rate in
the secret key generation problem is asymptotic which makes the problem NP-hard, while the minimal number of required
transmissions in the CDE problem is integer so that it can be solved by polynomial-time algorithms (as previously mentioned).
For solving the CCDE problem, only knowing the minimal number of required transmissions is not enough. It is also
necessary to design the coding scheme. Given the total number of transmissions, designing the coding scheme is a multicast
network code construction problem and can be solved by the polynomial time algorithm proposed by Jaggi et al. in [15].
C. Organization
This paper is organized as follows. Section II formally defines our system model and introduces definitions and notations
that would be used in this paper. Section III presents our main results. Section IV proposes our algorithms to compute the
minimal number of required transmissions for the basic CDE problem. Section V presents an efficient way to construct the
linear code. Section VI and Section VII show our method can be used to efficiently solve two generalized topic, CDE with
weighted cost and successive local omniscience. Section VIII concludes our work.
II. S YSTEM M ODEL AND D EFINITIONS
Before we formally introduce the problem, we define some notations. Let [n] denote the integer set {1, . . . , n}. For any
vector u, we use ui to denote the ith entry of u. For any matrix E, we use Eij to denote the entry at ith row j th column.
Let wH (u) denote the number of non-zero entries in vector u. For any set of vectors U = {u1 , u2 , . . . } and subset of vectors
S ⊆ U, let uS denote the bitwise OR (or, equivalently, the componentwise maximum) of all the vectors in the set S.
Consider a fully connected network which has N nodes and a desired file composed of K packets. Let N = [N ] and
P = {Pi , i ∈ [K]} denote the set of nodes and set of packets, respectively. Each Pi ∈ F, where F is some finite field. Without
loss of generality, we assume that every packet is initially available at least at two nodes and at most at N − 1 nodes1 . The set
of the packets initially available at node i is denoted
S as Xi (∀i ∈ N : Xi ⊆ P). The union set of the packets initially available
at a subset of node I ⊆ N is denoted as XI = i∈I Xi . We assume that all the nodes collectively have all packets, which
means XN = P. The notation XcI = P \ XI denotes the jointly missing packets at nodes in set I. Let M = mini∈N |Xi | be
the minimum number of initially available packets at any single node.
Definition 1. Define the packet distribution matrix E as the N × K matrix with entry at ith row j th column:
(
1,
Pj ∈ Xi
Eij =
0, otherwise

(1)

1 If there is a packet that is only initially available at one node, the optimal strategy is just letting that node send the uncoded packet to the others. If there
is a packet that is available at all nodes, then no one needs to recover it.

3

We will refer to the K-dimensional binary (row) vector ei , the ith row of E, as the Packet Distribution Vector (PDV) of node
i.
Let T = {T1 , . . . , TR } denote a linear coding scheme with R transmissions2 , which means that each transmission Ti is a linear
combination of packets available at the sender node. Let r = [r1 , . . . , rN ]T denote the rate vector where
Peach ri is the∗number
of transmissions made by node i. Hence, the total number of transmissions can be expressed as R = N
i=1 ri . Let R denote
the minimal number of required transmissions. Define the coefficient matrix as matrix A with entries aij (i ∈ [R], j ∈ [K]),
where αi = [ai1 , . . . , aiK ] and βj = [a1j , . . . , aRj ]T are the ith row and j th column vectors of A, respectively. Then we have:
  
 
    
T1
P1
P1
a11 a12 . . . a1K
P1
α1
 T2   a21 a22 . . . a2K   P2   α2   P2  

  P2 
  

    
=  .   .  = β1 β2 . . . βK  . 
(2)
 ..  =  ..



.
..
.
.
.
.
.
.
.
.
 .   .








.
.
. 
.
.
.
.
TR

aR1

aR2

...

PK

aRK

PK

PK

αR

It has been shown that any rate vector r which achieves universal recovery should satisfy the following Slepian-Wolf
constraints [16]:
X
ri ≥ |XcI | , ∀I ( N
(3)
i∈N\I

T

P

|XcI | , ∀I

( N} denote the set of all rate vectors r which satisfy (3). The minimal
Let Ω = {r = [r1 , . . . , rN ] : i∈N\I ri ≥
number of required transmissions for achieving universal recovery can be computed by solving the following integer linear
program:
R∗ = min
r∈Ω

Example 1. Consider a CDE problem for the fully
distribution matrix is as follows:

1
1
E=
0
1

N
X

ri .

(4)

i=1

connected network with N = 4 nodes and K = 9 packets. The packet
1
1
0
0

1
1
0
1

1
0
1
0

1
0
1
0

1
0
1
1

0
1
1
0

0
1
1
1


0
1

1
0

The number of non-empty proper subset of nodes is 18. Thus, we can write down 18 linear constraints and solve the
inequalities. For example, for I = {1}, the constraint for total number of transmissions made by nodes {2, 3, 4} is
X
ri ≥ |Xc1 | = 3
(5)
i={2,3,4}

By using the methods proposed in [4], [5], based on minimizing submodular function, the integer linear program can be
solved in polynomial time and the minimal number of required transmissions should be 5. After knowing the minimal number of
transmissions, generating the coding scheme is a multicast network code construction problem and can be solved by polynomial
time algorithms proposed in [15]. One feasible coding scheme could be: node 1 sends T1 = P1 + P5 and T2 = P2 + P6 , node
2 sends T3 = P3 + P7 , node 3 sends T4 = P4 + P8 and T5 = P9 .
In general, there are multiple different optimal coding schemes that achieve universal recovery. Although not all nodes
have to make transmissions, the existing algorithms which solve the integer linear program (4) have to consider constraints
introduced by all non-empty proper subset of nodes. In Example 1, the optimal coding scheme does not require node 4 to
make any transmission, but the algorithms still have to consider the constraints related to node 4. However, we will show
that without knowing the exact packet distribution information at some nodes (in this example, node 4), but only knowing the
number of initially available packets at them, it is still possible to compute the minimum number of required transmissions
and construct the optimal coding scheme which achieves universal recovery with the smallest number of transmissions.
Definition 2 ((d, K)-Basis). A set of K-dimensional binary linearly independent vectors (V = {vi : i ∈ [K − d]}, 0 ≤ d ≤
K − 1) is called a (d, K)-Basis if
wH (vS ) ≥ |S| + d,

∀∅ =
6 S ⊆ V.

(6)

Definition 3 (Balanced (d, K)-Basis). A (d, K)-Basis (V = {vi : i ∈ [K − d]}, 0 ≤ d ≤ K − 1) is called a balanced
(d, K)-Basis if
wH (vi ) = d + 1,
2 Only

∀i ∈ [K − d].

linear coding schemes are considered since it has been proved that they are sufficient to optimally solve the CDE problem [5], [7].

(7)

4

Condition (6) requires that wH (vS ), the number of dimensions spanned by vectors in S, be no less than the number of
vectors plus d. Hence, the number of vectors in each subspace of the K-dimensional space is limited.
Definition 4. A binary vector u can generate another binary vector v if u and v have the same dimension and
{m : vm = 1} ⊆ {n : un = 1}.

(8)

Moreover, let G(u) denote the set of all binary vectors that can be generated by u. Define G(S) = ∪u∈S G(u) and G(u, d) =
{v : v ∈ G(u), wH (v) = d + 1}.
Definition 5. A set of K-dimensional binary vectors U = {u1 , . . . , uL } is able to generate a (d, K)-Basis {vi : i ∈ [K − d]}
if ∀i ∈ [K − d], vi ∈ G(U, d). Let (d∗ , K)-Basis denote the (d, K)-Basis with largest d that can be generated by given vectors.
Lemma 1. If a set of K-dimensional binary vectors is able to generate a (d1 , K)-Basis, then it is also able to generate a
(d2 , K)-Basis for any d2 ≤ d1 .
Proof. Consider a set of binary vectors {u1 , . . . , uN } that is able to generate a (d1 , K)-Basis V = {v1 , . . . , vK−d1 }. Then
∀i ∈ [K − d1 ], ∃j ∈ [N ] : {m : vim } ⊆ {n : ujn }

(9)

Hence any vector generated by vi should also be able to be generated by the corresponding uj . Thus, to prove this lemma, it
suffices to show that ∀d2 ≤ d1 , there exists a (d2 , K)-Basis Q = {q1 , . . . , qK−d2 } that can be generated by {v1 , . . . , vK−d1 }.
Since V is a (d1 , K)-Basis and d2 ≤ d1 , ∀S ⊆ V, we have
wH (vS ) ≥ |S| + d1 ≥ |S| + d2

(10)

Thus all vectors in {v1 , . . . , vK−d1 } satisfy the constraints for vectors of (d2 , K)-Basis. We can choose qi = vi , ∀i = [K − d1 ].
Moreover, ∀j ∈ {K − d1 + 1, . . . , K − d2 }, we choose qj = v1 to be the repeated vector. Then, ∀Ŝ ⊆ Q:
wH (qŜ ) ≥ |Ŝ| + d1 − c ≥ |Ŝ| + d2

(11)

where c = |Ŝ ∩ {qj : j ∈ {K − d1 + 1, . . . , K − d2 }}| ≤ d1 − d2 is the number of the repeated vectors. Hence Q =
{q1 , . . . , qK−d2 } is a (d2 , K)-Basis.
III. M AIN R ESULTS
In this section, we present our main results and proofs. The relationship between a (d, K)-Basis and a coding scheme that
can enable nodes with at least d packets to recover all missing packets is revealed by the following theorem.
Theorem 1. If for some subset of nodes I ⊆ N there exists a (d, K)-Basis V ⊆ G({ei , i ∈ I}, d), then the nodes of I can
generate a coding scheme T = {T1 , . . . , TR } with R = K − d such that ∀i ∈ N, wH (ei ) ≥ d, node i can recover all packets.
Proof. In our coding scheme, each transmission Ti is a linear combination (with appropriate coefficients) of the packets indexed
by the non-zero entries in vi . Since the vectors vi ’s are a subset of the vectors generated by the PDVs of the nodes in I,
there is one node in I for each vi that can locally produce and transmit said linear combination. The overall code can thus be
characterized by a matrix A as in Eqn. (2) where in row i, only the elements indexed by vi are non-zero.
For any C ⊂ [K] with |C| = R, let A(C) denote the submatrix of A consisting of the R columns indexed by C. Due to
constraint (6), ∀∅ =
6 S ⊆ V , we have
wH (vS ) ≥ |S| + d.

(12)

Denote the ith of row of A(C) by αi (C). Then ∀Ŝ ⊆ {α1 (C), · · · , αR (C)}, we have
wH (αŜ (C)) ≥ wH (vŜ ) − d ≥ |Ŝ|.

(13)

Let G(A(C)) denote the bipartite graph corresponding to A(C), where there is an edge between ith left vertex and j th right
vertex if and only if A(C)ij 6= 0. Since Enq. (13) satisfies the condition of Hall’s marriage theorem, there exists a perfect
matching in G(A(C)). According to Edmond’s Theorem [17], the existence of perfect matching in bipartite graph G(A(C))
implies that det(A(C)) 6≡ 0.
Q
The product of determinants of all submatrices with R columns, denoted by C det(A(C)), is a multivariate polynomial of
non-zeros entries of A. For a large enough finite field, there always exists a good choice of non-zero entries of A such that
Q
C det(A(C)) 6≡ 0 [18]. For such choices, any R columns of A can be linearly independent at the same time. In other words,
given any d packets, the other R missing packets can be recovered from our coding scheme.
Remark 1. In Theorem 1, we proved that if the PDVs of nodes are able to generate a (d, K)-Basis, they can also generate a
coding scheme such that nodes with at least d packets can recover all missing packets from the coding scheme. The coefficient

5

matrix used in the proposed coding scheme can be associated with a constrained generator matrix for an MDS code [19]. We
will introduce an efficient way to construct it by performing elementary row operations on a Vandermonde matrix in Section V.
Theorem 1 characterizes a certain class of coding schemes. Their unique feature is that each transmission is a (judiciously
chosen) linear combination of exactly the same number of pure packets, namely, d + 1. Initially, this last feature may appear to
be too restrictive to attain optimal performance. However, in the sequel, we will establish in two steps that there always exists
an optimal scheme with this special property. Nonetheless, let us recall that in general, the optimal data exchange scheme is
not unique, so there may be alternative schemes attaining the same (optimal) number of transmissions while not satisfying
the special property. To establish existence of an optimal scheme with the special property, we will next establish that if a
(linear) scheme enabling universal recovery exists, then the nodes are also able to generate a corresponding basis (and hence,
by Theorem 1, a scheme with the special property must exist). More precisely, we have the following theorem:
Theorem 2. If a subset of nodes is able to generate a linear coding scheme with R (R = K − d) transmissions which achieves
universal recovery, then the PDVs of the nodes can generate a (d, K)-Basis V = {v1 . . . , vR }.
Proof. We assume that a subset of nodes I can generate R linearly independent transmissions T̂ = {T̂1 , . . . , T̂R } which
achieves universal recovery. The code can be charaterized by a matrix Â as in Eqn. (2) with rows α̂i ’s and columns β̂j ’s.
Let V̂ = {v̂1 , . . . , v̂R } where each vi = supp(α̂i ). That means in row i of Â, only the elements indexed by v̂i are non-zero.
We would like to show that if V̂ = {v̂1 , . . . , v̂R } does not satisfy Constraint (6) of the (d, K)-Basis, then the nodes which
generate the corresponding transmissions are able to add more packets into the linear combinations until the Constraint (6) is
satisfied.
For each non-empty subset S ⊆ {α̂1 , . . . , α̂R } such that wH (α̂S ) < |S| + d, we have
K − wH (α̂S ) > K − |S| − d ≥ R − |S| + 1

(14)

For the row vectors in S, at least R − |S| + 1 columns are all zeros. Hence, there must exist a subset of columns C ⊂ [K] and
corresponding subset of column vectors C ⊆ {β̂1 , . . . , β̂K } such that
|C| = |C| = R − |S| + 1

(15)

R − wH (β̂C ) ≥ |S| ⇒ wH (β̂C ) ≤ R − |S| < |C|

(16)

Let Â(C) denote the submatrix which is composed of the columns indicated by subset of column vectors C. Then submatrix
.
Â(C) is rank deficient. Let PC = {Pi : i ∈ C} denote the set of packets indexed by C. If the set N of nodes that generate
transmissions {T̂i : αi ∈ S} cannot add any more packets into the linear combination for their transmissions, they have no
more extra available packets in PC and each transmission is a linear combination of all its sender node’s available packets.
This assumption leads to a contradiction that nodes in N cannot recover all missing packets. Thus, nodes in N must have
more packets in PC and can add them into the linear combination to generate new transmissions {Ti : αi ∈ S} such that
wH (αS ) = |S| + d, where αi denotes the coefficient vector of transmission Ti . By replacing {T̂i : αi ∈ S} with {Ti : αi ∈ S},
we have a new coding scheme T such that the set of corresponding support vectors V = {vi , . . . , vR } forms a (d, K)-Basis.
For each transmission Ti and the corresponding T̂i , we have vˆi ∈ G(vi ). Given that T̂ can achieve universal recovery, T can
also achieve universal recovery.
Lemma 2. If a subset of nodes can generate a linear coding scheme based on (d, K)-Basis which enables nodes with at least
d packets to recover all packets, they also can generate an equivalent linear coding scheme based on balanced (d, K)-Basis.
Proof. For any linear coding scheme T = {T1 , . . . , TK−d } based on (d, K)-Basis V = {v1 , . . . , vK−d }, let A denote the
coefficient matrix of T and αi denote the ith row of A. For each Ti with wH (αi ) > d + 1, we show that it can be reduced
to a linear combination of d + 1 packets. ∀S̃ ⊆ {αj : j 6= i}, wH (αS̃ ) ≥ |S̃| + d. The linear combination of {Tj : j 6= i}
can provide K − d − 1 degree of freedoms among the used packets. Hence, by subtracting a proper linear combination of
{Tj : j 6= i} from Ti , we can get T̄i with wH (ᾱi ) = d + 1. Thus the corresponding V̄ is a balanced (d, K)-Basis.
Example 1 revisited. We already know a coding scheme with 5 transmissions that achieves universal recovery. But each coded
packet for transmission is a linear combination of two packets or just one pure packet. According to Theorem 2 and Lemma 2,
there must exist another coding scheme in which every coded packet for transmission is a linear combination of 5 packets. It
is easy to verify that coding scheme with the following coefficient matrix (over finite field GF (24 ) with primitive polynomial
α4 + α + 1) also achieves universal recovery.


5 4 4 1 1 0 0 0 0
15 11 14 14 0 1 0 0 0 



(17)
A=
 3 6 13 0 0 0 15 14 0 
 9 12 7 0 0 0 15 0 14
0 0 0 10 14 6 9 8 0

6

Each transmission is a linear combination of 5 packets. Define binary matrix V such that
(
1, Aij 6= 0
Vij =
0, Aij = 0
Then we have

  
v1
1
v2  1
  
 
V =
v3  = 1
v4  1
v5
0

1
1
1
1
0

1
1
1
1
0

1
1
0
0
1

1
0
0
0
1

0
1
0
0
1

0
0
1
1
1

0
0
1
0
1


0
0

0

1
0

(18)

(19)

The row vectors of V actually form a balanced (4, 9)-Basis. As mentioned in Theorem 1, given any 4 packets, the other 5
packets can be recovered from the coding scheme based on coefficient matrix A. Hence, in this example, the detail information
of available packets at node 4 is not necessary. As long as it initially has 4 packets, it can always recover the other packets
by receiving these coded packets.
Now we have the connection between optimal coding schemes with minimum number of required transmissions and balanced
(d, K)-Bases. Thus, we can search balanced (d, K)-Bases to get achievable (upper) bounds on the minimum number of
required transmissions. Extending the search over all values of d (and using Theorem 2 and Lemma 2) then establishes optimal
performance. More precisely, we have the following theorem:
Theorem 3. For the CDE in the fully connected network, the minimal number of required transmissions R∗ satisfies:
R∗ = K − min{M, d∗ }

(20)

where the (d∗ , K)-Basis is the largest (d, K)-Basis that can be generated by the PDVs of nodes.
Proof. By assumption, d∗ is the largest value of d for which a (d, K)-Basis can be generated by the PDVs. But then, by
Theorem 2, there does not exist any linear coding scheme that can achieve universal recovery by using fewer than K − d∗
transmissions.
Suppose that M ≥ d∗ . Then every node has at least d∗ packets. Since a (d∗ , K)-Basis can be generated by the PDVs,
according to Theorem 1, there is a linear coding scheme with K − d∗ transmissions such that every nodes with at least d∗
packets can recover all missing packets.
Now suppose that M < d∗ . According to Lemma 1, the PDVs can also generate a (d, K)-Basis with d = M. According
to Theorem 1, there is a linear coding scheme with K − M transmissions such that every nodes with at least M packets can
recover all missing packets.
Hence, the minimum number of required transmissions satisfies R∗ = K − min{M, d∗ }.
IV. A LGORITHM
According to Theorem 3, to solve the CDE problem for the fully connected network, we need to find the largest value of d
such that a (d, K)-Basis that can be generated by the PDVs of nodes. We denote this optimal value of d by d∗ . This problem
can be decomposed into two subproblems:
(1) Given a fixed d, determine whether any balanced (d, K)-Basis can be generated by the PDVs of nodes or not.
(2) Find the maximum value of d such that the PDVs of nodes can generate one balanced (d, K)-Basis.
A. Existence of (d, K)-Basis
Given the packet distribution matrix E and a specific parameter d, Algorithm 1 is proposed to check whether any balanced
(d, K)-Basis can be generated by the PDVs of nodes or not. Due to constraint (6), only nodes with at least d + 1 packets can
generate the (d, K)-Basis vectors. Hence, we only consider the PDVs with wH (ei ) > d as the candidates to generate basis
vectors.
Definition 6. For any binary vector u with wH (u) > d, let J = {j1 , . . . , jwH (u) } denote the set of indices of the non-zero
entries of u. Define the set B(u, d) = {bi : i ∈ [wH (u) − d]}, where bijk is the jkth entry of vector bi and satisfies
(
1, if k ∈ [d] ∪ {d + i} and jk ∈ J ,
bijk =
(21)
0,
otherwise.
The set B(u, d) is a particular set of binary vectors which are generated by u. Specifically, each of the vectors in the set has
weight d + 1 and it can be verified that the vectors satisfy the Constraint (6) of the definition of the (d, K)-Basis. Therefore,
they are basis vector candidates for balanced (d, K)-Basis.

7

Example 2. Given the e1 = [1, 1, 1, 1, 1, 1, 0, 0, 0], we can assign the B(e1 , 4) = {b1 , b2 } where b1 = [1, 1, 1, 1, 1, 0, 0, 0, 0]
and b2 = [1, 1, 1, 1, 0, 1, 0, 0, 0].
Lemma 3. For any binary vector v ∈ G(u, d) \ B(u, d), let S = B(u, d) ∪ {v}. We have wH (bS ) < |S| + d.
Proof. Since B(u, d) ⊂ G(u, d), wH (bB(u,d) ) ≤ wH (u). Also, according to the definition of B(u, d), we have
wH (bB(u,d) ) ≥ |B(u, d)| + d = wH (u)

(22)

Hence, wH (bB(u,d) ) = wH (u). For any v ∈ G(u, d) \ B(u, d), |S| = |B| + 1 = wH (u) − d + 1
wH (bS ) = wH (u) < wH (u) − d + 1 + d = |S| + d

(23)

Thus, any vector v ∈ G(u, d) \ B(u, d) is not compatible with B(u, d) in terms of the Constraint (6).
Corollary 1. For each PDV ei , it is sufficient to check vectors of B(ei , d) instead of all vectors of G(ei , d).

H (ei )
Although for each PDV ei , there are as many as wd+1
balanced (d, K)-Basis vectors that can be generated, we can select
any B(ei , d) and only consider them as the candidate basis vectors. Any other v ∈ G(ei , d) \ B(ei , d) can be ignored.
Lemma 4. Let S = {v1 , . . . , v|S| } denote a set of binary vectors with weight wH (vi ) = d + 1, ∀vi ∈ S and vS denote the
bitwise OR result of all vectors in S. For any vector v ∈ G(vS , d) \ S, let Ŝ = S ∪ {v}, we have wH (vŜ ) < |Ŝ| + d if
X
wH (vS ) ≤
wH (vi ) − (|S| − 1)d
(24)
i∈S

Proof. Since v and all vectors in S can be generated by vS , we have
X
wH (vŜ ) = wH (vS ) ≤
wH (vi ) − (|S| − 1)d

(25)

i∈S

=

X

(wH (vi ) − d) + d

(26)

i∈S

= |S| + d < |Ŝ| + d

(27)

Thus, any vector v ∈ G(vS , d) \ S is not compatible with S in terms of the Constraint (6) if Inequality (24) holds. Hence,
once we find any set of basis vectors that satisfy Inequality (40), any vector that can be generated by the merged vector should
not be consider.
Remark 2. Binary vector vm which has weight larger than d + 1 can be treated as a merged vector of B(vm , d). Therefore,
wH (vm ) − d = |B(vm , d)|. Condition (24) also works for the cases where some of the vectors have weight larger than d + 1.
We use set V to store the balanced (d, K)-Basis vectors that have been generated by previous PDVs and set Q to store
merged (d, K)-Basis vectors. Any set of vectors which satisfy Condition (24) will be merged as one vector and stored in Q.
Only b ∈ B(ei , d) that cannot be generated by any vector in Q can be selected as the basis vectors. After all vectors in B(ei , d)
have been checked, there must exist ei or a vector that can generate ei in Q.
In the subspace spanned by any two vectors in Q, there must exist at least one vector that should be added to form the
(d, K)-Basis. Instead of checking every subset of Q for merging, it is sufficient to only check the newly added vector with
any subset S ⊆ Q with |S| ≤ 2 and treat the merged vector as the newly added vector for further merging until no merging
possibility.
At the end, if K − d such vectors are found, the PDVs of nodes are able to generate a (d, K)-Basis which is stored by V
and the algorithm returns True and the corresponding basis V. Otherwise, return False.
B. Searching for d∗
We propose Algorithm 2 which uses binary search method to find the (d∗ , K)-Basis that can be generated by PDVs of nodes.
Let e∗ be the PDV of the node which has largest number of available packets initially, e∗ = arg maxei wH (ei ). According to
Theorem 3, if the PDVs of nodes can generate any (d, K)-Basis such that d ≥ M, we do not have to check for any larger d.
Also, the (d, K)-Basis with largest d that can be generated should alway be no larger than wH (e∗ ) − 1. Therefore, we start
from dmax = min{M, wH (e∗ ) − 1} instead of K.

8

Algorithm 1 Search balanced (d, K)-Basis (SdB)
1:
2:
3:
4:
5:
6:
7:
8:
9:

Input: E = [e1 , . . . , eN ]T and d.
Output: True, r, V or False.
Initialization: Q = ∅, V = ∅, r = [r1 , . . . , rN ]T = 01×N .
for i : i ∈ {1, . . . , N } do
for b ∈ B(ei , d) do
if b 6∈ G(Q, d) then
ri = ri + 1
V = V ∪ {b}
while ∃S ⊆ Q, |S| ≤ 2 : (28) holds do
X
wH (qS ∨ b) ≤
wH (qi ) + wH (b) − |S|d
qi ∈S

10:
11:
12:
13:
14:
15:
16:
17:
18:
19:

b = b ∨ qS , Q = Q \ S
end while
Q = Q ∪ {b}
end if
if |V| = K − d then
return True, r and V
end if
end for
end for
return False

Algorithm 2 Minimal Number of Required Transmissions and d-Basis
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:

Input: EN ×K = [e1 , . . . , eN ]T .
Output: R∗ , V∗
Initialization: dmin = 1, dmax = min{M, wH (e∗ ) − 1}.
(F, r, V) = SdB(E, dmax )
if F is True then
d∗ = dmax , V∗ = V
else
(F, r, V) = SdB(E, dmin )
if ¬F then
d∗ = 0, V∗ = IK
else
while dmax − dmin > 1 do
max
⌋
d = ⌊ dmin +d
2
(F, r, V) = SdB(E, d)
if F then
dmin = d, V∗ = V
else
dmax = d
end if
end while
d∗ = dmin
end if
end if
R∗ = K − d∗

(28)

9

C. Complexity
In Algorithm 2, binary search method is used to find the (d∗ , K)-Basis that can be generated by the PDVs of nodes which
has complexity bounded by log(K). For each specific d, Algorithm 1 is used to search the existence of (d, K)-Basis. Let
M (d) denote the number of nodes that have at least d + 1 packets. The first For loop has at most M (d) iterations. For the ith
candidate PDV ei , the size of set B(ei , d) satisfies |B(ei , d)| = wH (ei ) − d. Hence, the second For loop has at most wH (ei ) − d
th
iterations. The number of subsets of vectors in Q with size 1 and 2 are |Q| and |Q|
checked node,
2 , respectively. For the i
|Q| ≤ i, because basis vectors generated by the same PDV can always be merged to one vector and basis vectors generated by
different PDV may still be merged. The number of possible merging iteration for each
 candidate basis vector is less than the
size of (d, K)-Basis vector which is K − d. Then, the While loop has at most i + 2i (K − d) iterations for the ith PDV. Hence

PM(d)
the complexity3 of Algorithm 1 is bounded by i=1 (i + 2i )(wH (ei ) − d)(K − d)K. Since M (d) ≤ N and wH (ei ) ≤ K, we
have the overall complexity is bounded by O(N 3 K 3 log(K)), which is much lower than the complexity of existing algorithms
proposed in [4] based on minimizing a submodular function O((N 6 K 3 + N 7 ) log(K)) and algorithm based on subgradient
methods O((N 4 log(N ) + N 4 K 3 )K 2 log(K)).
Example 1 revisited. Apply our algorithms on Example 1. Node 4 and node 1 initially have the smallest and the largest
number of packets respectively, which means M = 4 and wH (e∗ ) = 6. Therefore we have dmax = 4. Algorithm 2 will first
check whether it is possible to generate a (4, 9)-Basis from {e1 , e2 , e3 } by SdB(E, 4). The PDV of the 4th node, e4 , will not
be considered as the candidate, since wH (e4 ) = 4 and it can not generate any binary vector with 5 ones. In this example,
SdB(E, 4) returns True. The minimal number of required transmissions is 5. For general cases, if (dmax , K)-Basis cannot
be generated, binary search method would be used to find the d∗ .
Now we investigate the detail of Sdb(E, 4). The first For loop only runs for {e1 , e2 , e3 }.
• For e1 , B(e1 , 4) = {b11 , b12 } where b11 = [1, 1, 1, 1, 1, 0, 0, 0, 0] and b12 = [1, 1, 1, 1, 0, 1, 0, 0, 0].
• For e2 , B(e2 , 4) = {b21 , b22 } where b21 = [1, 1, 1, 0, 0, 0, 1, 1, 0] and b22 = [1, 1, 1, 0, 0, 0, 1, 0, 1].
• For e3 , B(e3 , 4) = {b31 , b32 } where b31 = [0, 0, 0, 1, 1, 1, 1, 1, 0] and b32 = [0, 0, 0, 1, 1, 1, 1, 1, 1].
The second For loop runs for each bij ∈ B(ei , 4).
• For b11 , since Q = ∅, b11 will be added into V as v1 and Q as q1 directly.
• For b12 , since it cannot be generated by q1 , b12 will be added into V as v2 . Now, Q is not empty and has q1 . We have to
check whether b12 should be merged with q1 as one vector or not. Since wH (b12 ∨ q1 ) ≤ wH (b12 ) + wH (q1 ) − d satisfies
Inequality (28). We should merge them and update as q1 = [1, 1, 1, 1, 1, 1, 0, 0, 0] 4 .
• For b21 , since it cannot be generated by q1 , b21 will be added into V as v3 . The merging possibility between b21 and q1
will be checked and it turns out that they should not be merged. Hence b21 will be added into Q as q2 .
• For b22 , since it cannot be generated by q1 or q2 , b22 will be added into V as v4 . It can be verified that b22 should be
merged with q2 but not with q1 . Hence q2 is updated as q2 = [1, 1, 1, 0, 0, 0, 1, 1, 1].
• For b31 , since it cannot be generated by q1 or q2 , b31 will be added into V as v5 . Now we have enough (4, 9)-Basis
vectors. The algorithm SdB(E, 4) will return True and corresponding V shown as Equation (19).
Actually, if we check the merging possibility between b31 and {q1 , q2 }, we will find that b31 should not be merged with q1 or
q2 individually, but should be merged with them together. And when we have the complete (d, K)-Basis, we can always merge
all vectors in Q into one vector with K ones. Although b32 is in B(e3 , 4), it is not used, because we got enough basis vectors
before its iteration.
V. C ODE C ONSTRUCTION
In previous sections, we presented how to compute the minimum number of required transmissions and the corresponding
algorithms. To completely solve the CDE problem, we still need to give the coding scheme which achieves universal recovery
by using the minimum number of transmissions. In this section, we explain how to explicitly design the optimal coding scheme.
After knowing the number of transmissions which should be made by each node, designing the coding scheme can be
formulated as a multicast network code construction problem. Methods based on the mixed matrix completion algorithm [20]
and the Jaggi et al. algorithm [15] are presented in [4]. However, those methods have to take all packet distribution information
into consideration and generate a coding scheme that may only works for this particular setting. As Theorem 1 pointed out, it
is possible to construct a coding scheme which enables universal recovery at all nodes with at least K − R∗ packets. Packet
distribution information of nodes which do not send anything is not necessary for constructing the code and can be ignored.
This class of codes is based on MDS codes which can be constructed efficiently by starting from Vandermonde matrices.
3 Computing bitwise AND or OR of two K-dimensional binary vector has complexity of K basic operations. In step 6, we compute bitwise OR between
b and each vector in Q and this results are also used in merging checking. Hence complexity of step 6 is not considered.
4 In fact, b
12 and q1 can be merged without checking Condition (40), since q1 = b11 and b12 are generated by the same PDV, e1 .

10

Consider an R × K Vandermonde matrix over a finite field Fq ,

1
1
1
 θ1
θ
θ
2
3

V =  ..
..
..
 .
.
.
θ1R−1 θ2R−1 θ3R−1

where R = K − d:
...
...
..
.

1
θK−1
..
.

1
θK
..
.

...

R−1
θK−1

R−1
θK







(29)

For large enough q, there exists {θ1 , . . . , θK } such that any m (m ≤ R) columns of V are linearly independent. Apparently
V is the generator matrix of an MDS code. However, the coefficient matrix A cannot simply be set equal to V, since the
number of non-zero entries of each row cannot be larger than the number of available packets at the node which generates
this transmission. Nevertheless, by performing elementary transformations on V, we can transform it into a coefficient matrix
A with the property that each row has K − R + 1 non-zero entries.
Lemma 5. For any R × K (R ≤ K) Vandermonde matrix V, by performing elementary row operations on V, it is possible
to get a matrix A with row vectors {α1 , . . . , αR } such that
wH (αi ) = K − R + 1
wH (αS ) ≥ |S| + K − R

∀i ∈ [K − R]
∅ 6= S ⊆ {α1 , . . . , αR }

(30)
(31)

Proof. Suppose we have a R × K Vandermonde matrix depicted as Eqn. (29). We use
 Vl and Vr to denote the first R columns
submatrix and the last K − R columns submatrix of V, respectively. Then, V = Vl Vr . Since any R columns of V are
linearly independent, Vl is always a full rank matrix and invertible. Performing elementary row operations on V is equivalent
to left multiplying a R × R matrix to V. Let D denote a R × R matrix and D = Vl−1 .

 

(32)
DV = D Vl Vr = IR DVr

where IR is the R × R identity matrix. Since D is invertible and is a full rank matrix, we have
rank(DVr ) = rank(Vr ) = K − R

(33)

Hence, DVr is a column full rank matrix and each row could have K − R non-zero entries. Let A = DV, then we have row
vectors of A satisfy
wH (αi ) = 1 + K − R
wH (αS ) ≥ |S| + K − R

∀i ∈ [K − R]
∅ 6= S ⊆ {α1 , . . . , αR }

(34)
(35)

The matrix DV with D = Vl−1 satisfies both conditions of the balanced (d, K)-Basis with d = K − R. Hence it can be a
coefficient matrix for the coding scheme based on the (d, K)-Basis. Normally, the places of non-zero entries of the (d, K)-Basis
generated by the PDVs of nodes are different from matrix DV. However, since any row vector with d + 1 ones is in the space
spanned by row vectors of DV, further elementary row operations can be performed on DV to get the coefficient matrix with
non-zeros entries at the same places as the (d, K)-Basis generated by the PDVs of nodes.
Example 1 revisited. Now we show how to use a Vandermonde matrix to construct the linear coding scheme for Example 1.
We know that R∗ = 5 and there exists a (4, 9)-Basis V . Consider the Vandermonde matrix V over the finite field GF (24 ) with
primitive polynomial α4 + α + 1.


1 1 1 1 1 1 1 1 1
1 2 3 4 5 6 7 8 9 



(36)
V =
1 4 5 3 2 7 6 12 13
1 8 15 12 10 1 1 10 15
1 3 2 5 4 6 7 15 14

By elementary row transformations and Gaussian eliminations, we can get the coefficient matrix A shown as (17). Given any
four packets, the other packets can be recovered from transmissions based on A. Suppose there is another node with PDV
e5 = [1, 0, 1, 0, 1, 0, 0, 1, 0]. It can also recover all its missing packets by receiving transmissions based on A. The detail of its
packet distribution information is not used for either computing the minimal number of required transmissions or designing
the coding scheme. Although in this example the coefficient matrix of our method looks more complicated than that of methods
based on Jaggi et al.’s algorithm, in general cases, the complexity of constructing the coefficient matrix via our method is
much lower.

11

VI. W EIGHTED C OST

OF

T RANSMISSIONS

In the basic CDE problem, every transmission incurs the same cost, irrespective of the transmitting node. However, in more
general cases, it is intuitive to consider that the (transmit) cost for different nodes are different. Let w = [w1 , . . . , wN ]T denote
the weight vector where each wi is the cost for node i to make one P
transmission. For any coding scheme with rate vector
N
r = [r1 , . . . , rN ]T , the weighted cost is denoted by C(r) = wT · r = i=1 wi ri . Instead of minimizing the total number of
transmissions (sum rate), the goal of the CDE problem with weighted cost is to achieve universal recovery by a coding scheme
with rate vector which has the minimum weighted cost. Note that once the optimal rate vector is found, a corresponding
optimal transmission scheme can be developed exactly along the lines of the unweighted case discussed earlier.
The minimum weighted cost for the CDE problem with weighted cost can be computed as
C ∗ = min C(r) = min
r∈Ω

r∈Ω

N
X

wi ri .

(37)

i=1

Although the optimization should be over all vectors in Ω, we can actually decompose this optimization problem into two
sub-optimization problems. We first find the optimal rate vector under the conditional that the sum rate is fixed. Then, the
further optimization should only be over the optimal rate vectors for different fixed sum rates.
Definition 7. Let K(R) denote the minimum weighted cost of all rate vectors that can achieve universal recovery and has
sum-rate equal to R.
K(R) =

min

r∈Ω,S(r)=R

C(r) =

min

r∈Ω,S(r)=R

N
X

wi ri

(38)

i=1

Let Rmin denote the minimum sum rate such that rate vector can achieve universal recovery5. Only rate vectors with sum
rate between Rmin and K should be considered. The minimum weighted cost can also be computed as
C∗ =
=

min

R∈{Rmin ,...,K}

K(R)

min

min

R∈{Rmin ,...,K} r∈Ω,S(r)=R

N
X

wi ri

(39)

i=1

Example 3. Consider a CDE problem for the fully connected network with 5 nodes and 9 packets with the goal of minimizing
the weighted cost of transmissions. The packet distribution matrix (PDM) is as following:


0 1 0 1 0 0 1 1 1
1 0 0 0 1 1 0 1 1



E=
0 1 1 0 0 1 0 1 1
1 0 1 0 1 1 0 1 0
1 1 0 1 1 0 1 0 1
The weights of nodes are as following:

Node(i)
wi

1
2

2
3

3
6

4
8

5
10

By using the methods proposed in [4], [9], we can find that the optimal rate vector is r∗ = [3, 3, 1, 0, 0]T and the minimum
weighted cost is 21. However, for the basic CDE problem (unweighted case) with the same packet distribution matrix, the
optimal rate vector is r = [1, 1, 1, 1, 1]T.
Remark 3. By using algorithm in [5], [4], [21], we can show that the minimum sum rate Rmin for Example 3 is 5. But for
CDE problem with weighted cost, the optimal rate vector has sum rate 7, which is larger than the minimum required sum rate.
Thus, only finding the rate vector with sum rate Rmin is not enough, we have to optimize K(R) over all R ∈ {Rmin , . . . , K}.
However, we show that it is not necessary to compute K(R) for all R ∈ {Rmin , . . . , K}. By exploiting the convexity of the
function K(R), we can search the optimal R and rate vector by the binary searching method.
We propose an efficient deterministic algorithm based on (d, K)-Basis to solve the optimization problem (38). For a given
fixed number of transmission R, Algorithm 3 searches the existence of corresponding (d, K)-Basis where d = K − R.
Theorem 4. For any R ∈ {Rmin ,P
. . . , K} and d = K − R, let r = [r1 , . . . , rN ]T be the output rate vector of Algorithm 3
N
with input E and d, then K(R) = i=1 wi ri .

5 In previous sections, for basic CDE problem, we use R∗ to denote the minimum sum rate such that universal recovery can be achieved. However, in CDE
problem with weighted cost, the optimal rate vector may not have minimum sum rate.

12

Algorithm 3 Search (d, K)-Basis (SdB)
1:
2:
3:
4:
5:
6:
7:
8:
9:

Input: E = [e1 , . . . , eN ]T (wi ≤ wj ∀i ≤ j) and d.
Output: True, r, V or False.
Initialization: Q = ∅, V = ∅, r = [r1 , . . . , rN ]T = 01×N .
for i : i ∈ {1, . . . , N } do
for b ∈ B(ei , d) do
if b 6∈ G(Q, d) then
ri = ri + 1
V = V ∪ {b}
while ∃S ⊆ Q, |S| ≤ 2 : (40) holds do
X
wH (qS ∨ b) ≤
wH (qi ) + wH (b) − |S|d

(40)

qi ∈S

10:
11:
12:
13:
14:
15:
16:
17:
18:
19:

b = b ∨ qS , Q = Q \ S
end while
Q = Q ∪ {b}
end if
if |V| = K − d then
return True, r and V
end if
end for
end for
return False

The details of the proof of Theorem 4 are given in Appendix A, but for a brief outline, we may observe that for any other
rate vector which has the same sum rate as the rate vector r output by Algorithm 3, we must have either (1) if it can achieve
universal recovery, it has equal or larger weighted cost than r; or (2) it cannot achieve universal recovery, hence it should not
be considered.
Remark 4. In words, Theorem 4 says that the output rate vector of Algorithm 3 is the optimal rate vector which has the
minimum weighted cost among all the rate vectors which have sum rate R and can achieve universal recovery.
Comparing to Algorithm 1 which checks the existence of a balanced (d, K)-Basis for the basic CDE problem and outputs
the corresponding (d, K)-Basis vectors if they exist, Algorithm 3 requires that the input PDVs be ordered according to their
weights. The nodes with smaller weights have smaller indices. The node with the smallest weight would be selected to generate
as many (d, K)-Basis vectors as it can. Then, the nodes with larger weights would be selected to generate (d, K)-Basis vectors
that can not be generated by previous nodes. We show that by ordering the input PDVs in ascending order of their weights,
Algorithm 3 can find the optimal rate vector and corresponding (d, K)-Basis vectors which can achieve universal recovery by
using K − d transmissions and has minimum overall weighted cost. The ordering of the PDVs according to their weights can
be done before the start of Algorithm 3 and only requires complexity O(log(N )). As compared to the complexity of searching
the existence of a (d, K)-Basis, which is O(N 3 K 3 ), the complexity of pre-ordering nodes can be ignored.
Now we have a method to get the optimal solution to the sub-optimization problem (38). In order to get the globally
optimal solution to optimization problem (39), it is sufficient to only consider the rate vectors that are output by Algorithm 3
with different values of input parameter d (d = K − R). However, it is not necessary to run Algorithm 3 with all possible
R ∈ {Rmin , . . . , K}, by leveraging convexity of the function K(R) which is stated by the following Theorem and hence the
optimal weighted cost and rate vector can be found by a binary search style method.
P
Theorem 5. For Rmin ≤ R ≤ K, the function defined by (38): K(R) = minr∈Ω,S(r)=R N
i=1 wi ri is convex.

The proof is given in Appendix B. To prove Theorem 5, it is sufficient to only consider coding schemes with rate vectors
output by Algorithm 3, since they are the conditionally optimal solution for fixed sum rate R. In particular, we exploit
some properties of rate vector output by Algorithm 3 to show that the second order difference of K(R) is non-negative, i.e.
K(R + 2) + K(R) − 2K(R + 1) ≥ 0. By induction, we prove that K(R) is a convex function of R.
Remark 5. In [4], it has been proved that the function K(R) defined in (38) is convex for Rmin ≤ R ≤ K for a relaxed
condition where each entry of r = [r1 , . . . , rN ]T can be non-integer rate vector. However, the rate vector should always be
integer for the cooperative data exchange problem. The improvement of our theorem is we prove that for integer rate vectors,
the function K(R) defined in (38) is still convex for Rmin ≤ R ≤ K.
Since the function K(R) is a convex function, it is not necessary to search all possible R to get the optimal solution to

13

optimization problem (39). We propose Algorithm 4 to compute the minimum weighted cost by using a binary searching style
method.
Algorithm 4 Finding r∗ and C ∗ using Binary Search Algorithm
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:

Input: E = [e1 , . . . , eN ]T , K and w = [w1 , . . . , wN ]T such that (wi ≤ wj ∀i ≤ j)
Output: r∗ and C ∗
Initialization: dstart = 0, dend = M
while dstart < dend do
d = max{⌊ dstart2+dend ⌋, dstart + 1}
(F, r, V) = SdB(E, d)
if F is False then
dend = d
else
dˆ = d − 1
ˆ
(F̂ , r̂, V̂) = SdB(E, d)
if wT · r > wT · r̂ then
ˆ r∗ = r̂
dend = d,
else
dstart = d, r∗ = r
end if
end if
end while
R∗ = K − d, C ∗ = wT · r

The complexity of the binary search of Algorithm 4 is approximately O(log(K)). Hence, the overall complexity of our two
algorithms is O(N 3 K 3 log(K)) which is the same as complexity as the complexity of algorithms for basic CDE problem.
Example 3 revisited. On applying Algorithm 3 on Example 3 for d = {0, 1, 2, 3, 4}, we can get the results as shown in
Table I. As can be seen from the table, the minimum cost is achieved by a coding scheme that uses 7 transmissions, which is
Table I
S UM RATE , OPTIMAL WEIGHTED COST AND RATE VECTOR
d
4
3
2
1
0

R=K-d
5
6
7
8
9

K(R)
29
22
21
23
25

r1
1
2
3
4
5

r2
1
2
3
3
3

r3
1
2
1
1
1

r4
1
0
0
0
0

r5
1
0
0
0
0

larger than the minimum number of required transmissions (Rmin = 5) for achieving universal recovery. Additionally, if we
plot the function K(R) vs R for example 3 and connect the points, it is easy to see the convexity in Fig. 1.
30

K(R)

28
26
24
22
20

5

6

7

8

9

R

Figure 1. Optimal weighted cost (K(R)) vs Sum rate (R) for Example 3.

VII. S UCCESSIVE L OCAL O MNISCIENCE
In the basic CDE problems, all nodes have the same priority and should be able to recover all packets at the end of the
communication phase. In this section, we consider a generalized problem called Successive Local Omniscience (SLO)[22]

14

where nodes have different priorities. Specifically, let G = {G1 , . . . , GM } be a partition of node set N. In the SLO problem,
communication occurs in M rounds, numbered from 1 to M and taking place in this order, as follows:
def
• In round i, only the nodes in the set G[i] = ∪ij=1 Gj are allowed to transmit.
• After round i, all nodes in the set G[i] must be able to recover all packets that were initially present at all the nodes in
the set G[i] .
In this sense, if i < k, then nodes in Gi can be thought of as having priority over nodes in Gk (although in the general case,
no node is guaranteed to attain full omniscience of all packets before the end of the last round).
i T
Let ri = [r1i , . . . , rN
] denote the accumulated rate vector up to and including the ith round, where each rji denotes the total
number of transmissions made by node j from the first round to the ith round. The corresponding entries of rate vectors ri and
ri+1 satisfy rji ≤ rji+1 for every node j ∈ N. Let Ω(G[i] ) be the set of rate vectors up to and including the ith communication
round satisfying
X
(41)
rji ≥ XG[i] \ XI , ∀I ( G[i]
j∈G[i] \I

Then we have the following lemma characterizing solutions to the SLO problem:
Lemma 6. Any solution to the SLO problem is also a solution to the following multi-objective linear program:
min

ri ∈Ω(G[i] )

N
X

rji , ∀i ∈ [M ]

(42)

j=1

Proof. For any i ∈ [M ], rate vectors ri ∈ Ω(G[i] ) satisfy the Slepian-Wolf constraints for achieving local omniscience and only
nodes in G[i] are allowed to make transmissions. The minimization gives the minimum sum rate. Thus, for M communication
rounds, the overall optimal solutions achieve successive local omniscience.
The main goal and contribution of this section is to present a more efficient solution of the SLO problem via the (d, K)-Basis
method. Let EG[i] denote the packet distribution matrix of the nodes in G[i] . If we run Algorithm 2 with EG[i] as input in the
subspace indexed by the collectively available packets of G[i] , it will return the minimum number of required transmissions
for achieving local omniscience as well as the corresponding (d, Ki )-Basis vectors. Algorithm 2 can be called for every EG[i] ,
i ∈ [M ] and we can get the di -Basis vectors for local omniscience achieved by each G[i] . If di ≥ di+1 , the di -Basis vectors
can also be used to generate di+1 -Basis vectors by adding 0’s to the dimensions that are added by packets in XG[i+1] \ XG[i] . If
di < di+1 , the di -Basis vectors cannot be used to generate di+1 -Basis vectors. Hence, the optimal strategy is to use the coding
scheme based on di -Basis in the subspace indexed by packets of XG[i+1] so that every transmissions used in the previous
round are useful in the current round.
Theorem 6. For successive local omniscience problem with G[i] and corresponding packet distribution submatrix EG[i] , for
i ∈ [M ], the minimum number of required transmissions Ri∗ for round i is
Ri∗ = Ki − min{Mi , d∗1 , . . . , d∗i }

(43)

where Ki = |XG[i] | is the number of packets collectively available at nodes in G[i] , Mi = minj∈G[i] |Xj | is the minimum
number of available packets at any single node in G[i] and d∗i is the maximum (d, Ki )-Basis that can be generated by PDVs
of nodes in G[i] .
Proof. For the first round, R1∗ = K1 − min{M1 , d∗1 }, according to Theorem 3. For the ith round, since G[j] ⊂ G[i] ,
∀j < i, Mi ≤ Mj . According to Theorem 3, nodes in G[i] can generate a coding scheme based on {Mi , d∗i }-Basis can
achieve local omniscience. If d∗i = min{d∗1 . . . , d∗i }, and all transmissions used in previous rounds can also be used as the
transmissions of coding schemes based on {Mi , d∗i }-Basis. Thus, in the ith round, only additional transmissions are required
and the total minimum number of required transmissions for achieving local omniscience is Ri∗ = Ki − min{Mi , d∗i }. If
d∗j = min{d∗1 . . . , d∗i } and j < i, then transmissions generated in the j th round cannot all be used for coding scheme based on
{Mi , d∗i }-Basis. In order to make use of all previously generated transmissions, coding scheme based on {Mi , d∗j }-Basis can
be used to achieve local omniscience for nodes in G[i] and the total number of required transmissions is Ri∗ = Ki − {Mi , d∗j }.
Therefore, Ri∗ = Ki − min{Mi , d∗1 , . . . , d∗i }.
We propose Algorithm 5 to compute the minimum number of required transmissions (Ri∗ ) and the local optimal rate vector
for nodes in each group with different priorities. Algorithm 5 iteratively calls Algorithm 1 to find the existence of
(d, Ki )-Basis that can be generated for linear coding scheme to achieve local omniscience.
Based on the (d, Ki )-Basis vectors Vi∗ and local optimal rate vector ri∗ , the corresponding linear coding scheme can be
generated to achieve local omniscience. Instead of generating linear coding scheme for each communication round individually,
it is possible to globally generate a linear coding scheme in which the first Ri∗ transmissions can achieve local omniscience.
In terms of the complexity of our approach, in each communication round, the minimum number of required transmissions
and the accumulated rate vector are found by using binary search method and iteratively call Algorithm 1. The total number
(r∗i )

15

Algorithm 5 Successive Local Omniscience
1: Input: E = [e1 , . . . , eN ]T and G = {G1 , . . . , GM }
∗
2: Output: R1∗ , . . . , RM
and r∗1 , . . . , r∗M
∗
3: Initialization: d = K
4: for i = 1 . . . M do
5:
dmin = 1, dmax = min{Mi , d∗ }
6:
(F, r, V) = SdB(EG[i] , dend )
7:
if F is True then
8:
d∗i = dmax , Vi∗ = V, r∗i = r
9:
else
10:
(F, r, V) = SdB(EG[i] , dmin )
11:
if F is False then
12:
d∗i = 0, Vi∗ = IKi
13:
else
14:
while dmax − dmin > 1 do
max
15:
d = ⌊ dmin +d
⌋
2
16:
(F, r, V) = SdB(E, d)
17:
if F is True then
18:
dmin = d, d∗i = d, Vi∗ = V, r∗i = r
19:
else
20:
dmax = d
21:
end if
22:
end while
23:
end if
24:
end if
25:
d∗ = d∗i , Ri∗ = Ki − d∗i
26: end for
of outer iteration is equal to the number of priority groups, M . The binary search method for the ith round has complexity
bounded by O(log(Ki )). For the ith round, Algorithm 1 has complexity bounded by O(|G[i] |3 Ki3 ), since the number of
nodes and packets considered in the ith round are |G[i] | and Ki , respectively. Hence, the total number of computation can be
PM
expressed as i=1 |G[i] |3 Ki3 log(Ki ). Since ∀i : |G[i] | ≤ N and Ki ≤ K, the overall complexity of our (d, K)-Basis method
for solving SLO problem is bounded by O(N 3 K 3 M log(K)).
Example 4. Consider the successive local omniscience

1 1
0 1

1 1
E=
0 0

1 0
1 1

problem with packet distribution matrix

1 1 0 0 0 0 0
1 1 1 0 0 0 0

0 0 0 1 0 0 0

1 1 0 0 1 0 0

1 1 1 1 1 1 0
1 1 1 0 1 0 1

(44)

And the nodes are partitioned into three groups with decreasing priorities: G1 = {1, 2}, G2 = {3, 4} and G3 = {5, 6}. Since
nodes in G1 collectively only have packets P1 , . . . , P5 , the optimization for the first communication round is equivalent to the
basic CDE problem with packet distribution matrix EG1 , which is a submatrix of the first two rows of E.


1 1 1 1 0
EG1 =
(45)
0 1 1 1 1
It is apparent that only two transmissions are required to achieve local omniscience for G1 . Consider the following two coding
schemes:
• Coding scheme 1: Node 1 sends P1 and Node 2 sends P5 .
• Coding scheme 2: Node 2 sends P1 + P2 + P3 + P4 and Node 2 sends P2 + P3 + P4 + P5 .
In Coding scheme 1, each transmission is a linear combination of as few packets as possible, while in Coding scheme 2,
each transmission is a linear combination of as many packets as possible. Both coding schemes can enable two nodes to fully
recover packets that are collectively available at them. However, we will show that Coding scheme 1 is suboptimal but Coding
scheme 2 is optimal. In the second communication round, the goal is to enable node in G[2] to recover packets which are

16

collectively available at them. Similarly, we have packet distribution
of E.

1 1 1 1
0 1 1 1
EG[2] = 
1 1 0 0
0 0 1 1

matrix EG[2] , which is a submatrix of the first four rows
0
1
0
0

0
0
1
0


0
0

0
1

(46)

If we treat this as a packet distribution matrix of a basic CDE problem, it is easy to find that the minimum number of required
transmission is 5, since the (2, 7)-Basis is the (d, 7)-Basis with largest d value that can be generated by row vectors of EG[2] .
And this implies that in the successive local omniscience problem, the total number of required transmissions is at least 5. If
we choose Coding scheme 1 in the first transmission round, the packet distribution matrix becomes


1 1 1 1 1 0 0
1 1 1 1 1 0 0

ÊG[2] = 
(47)
1 1 0 0 1 1 0
1 0 1 1 1 0 1
As the row vectors of ÊG[2] can only generate a (3, 7)-Basis which has largest d value, 4 transmissions are required in the
second communication round to achieve local omniscience for nodes in G[2] . Hence, the total number of transmissions for
the first and second rounds is 2 + 4 = 6 which is larger than the lower bound 5. However, if coding scheme 2 is chosen in
the first round, actually it is possible to generate a coding scheme based on (2, 7)-Basis in which the first two transmissions
achieve local omniscience for nodes in G1 . The desired (2, 7)-Basis generated by EG[2] is
  

v1
1 1 1 1 0 0 0
v2  0 1 1 1 1 0 0
  

v3  = 0 1 1 1 1 0 0
(48)
  

v4  1 1 0 0 0 1 0
v5
0 0 1 1 0 0 1

As you can see the first 5 columns of v1 and v2 can actually form a (3, 5)-Basis. And the coding scheme based on them can
achieve local omniscience for nodes in G1 . Similarly, we can show that 2 transmissions are required in the third communication
round to achieve omniscience for nodes in G[3] . Instead of generating coefficients for linear combinations of packets for each
round individually, we can deal with them together by constructing a linear coding scheme based on the final (d, K)-Basis
we need, which is (2, 9)-Basis in this case. Given the rate vector in each round:
r1 = [1, 1, 0, 0, 0, 0]T

(49)

r2 = [0, 1, 1, 1, 0, 0]

T

(50)

r3 = [0, 0, 0, 0, 1, 1]

T

(51)

And the (2, 9)-Basis that generated by row vectors of
  
v1
1
v2  0
  
v3  0
  
v4  = 1
  
v5  0
  
v6  1
v7
1

E
1
1
1
1
0
0
1

1
1
1
0
1
1
1

1
1
1
0
1
1
1

0
1
1
0
0
1
1

0
0
0
1
0
1
0

0
0
0
0
1
1
1

0
0
0
0
0
1
0

By using the coding construction method based on MDS code in Section V, we
all entries are over finite file GF (24 ) with primitive polynomial α4 + α + 1.
  
a1
4 7 3 1 0 0 0
a2   0 8 12 3 2 0 0
  
a3   0 13 13 2 2 0 0
  
a4  = 15 8 0 0 0 1 0
  
a5   0 0 4 5 0 0 10
  
a6  10 0 9 9 5 5 5
a7
9 4 1 1 1 0 1


0
0

0

0

0

0
1

(52)

can get a coefficient matrix as follows, where
0
0
0
0
0
5
0


0
0

0

0

0

0
1

(53)

It can be verified that the first 2 transmissions achieves local omniscience for nodes in G1 , the first 5 transmissions achieve
local omniscience for nodes in G[2] , and all transmissions together achieve omniscience for nodes in G[3] (all nodes).

17

VIII. C ONCLUSION
In this paper, we introduce the notion of the (d, K)-Basis. We establish that the existence of such a basis is both a necessary
and sufficient condition for the existence of coding schemes that can achieve universal recovery with K −d transmissions for the
fully connected network. We provide a polynomial-time deterministic algorithm based on the (d, K)-basis construction which
solves the cooperative data exchange problem. We show that we can efficiently construct the coefficients of an optimal linear
coding scheme starting from a Vandermonde matrix by levering the connection between the (d, K)-Basis and maximum distance
separable codes. Moreover, we demonstrate that our (d, K)-Basis construction method can also be used in solving generalized
versions of the cooperative data exchange problem, including with weighted cost and with successive local omniscience.
ACKNOWLEDGMENT
This work was supported in part by the Swiss National Science Foundation under Grant 169294. The authors thank Abhin
Shah for his contribution for Section VI during his summer internship at EPFL.
A PPENDIX
A. Proof of Theorem 4
In order to prove Theorem 4, we first prove two useful Lemmas.
∗ T
Lemma 7. Let r∗ = [r1∗ , r2∗ , . . . , rN
] denote the rate vector output by Algorithm 3. For any rate vector r = [r1 , . . . , rN ]T
∗
such that r ∈ Ω and S(r ) = S(r), there does not exists any node pair (i, j) such that i < j, ri > ri∗ and rj < rj∗ .

Proof. If the coding scheme with rate vector r can achieve universal recovery and uses the same total number of transmissions,
then the coding scheme can be implemented as a (d, K)-Basis based coding scheme which has the same d value as thePcoding
N
scheme with rate vector r∗ . As Algorithm 3 guarantees that ∀i ∈ [N ], if ri∗ > 0, then there must exist as many as j=i rj∗
∗
∗
(d, K)-Basis vectors that cannot be generated by nodes in set {1, 2, . . . , i − 1}. If ∃i < j such that, ri > ri and rj < rj , then
PN
PN ∗
j=i rj <
j=i rj which is not possible as such vectors can only be generated by nodes in set {i, i + 1 . . . , N }. Hence, it
is impossible that ∃i < j: ri > ri∗ and rj < rj∗ .
∗ T
Lemma 8. Let r∗ = [r1∗ , r2∗ , . . . , rN
] denote the rate vector output by Algorithm 3. If there exists a coding scheme with rate
T
vector r = [r1 , . . . , rN ] such that r ∈ Ω, S(r∗ ) = S(r). If there exists node pair (i,j) such that i < j, ri < ri∗ and rj > rj∗ ,
then C(r) ≥ C(r∗ ).

Proof. Let S1 = {i : ri < ri∗ }, S2 = {j : rj > rj∗ } and S3 = {k : rk = rk∗ }. Since S(r∗ ) = S(r) , we have
0=

N
X

(ri − ri∗ ) =

i=0

X

(ri − ri∗ ) +

i∈S1

=

X

X

(rj − rj∗ ) +

j∈S2

(ri − ri∗ ) +

i∈S1

X

X

(rk − rk∗ )

(54)

k∈S3

(rj − rj∗ )

(55)

j∈S2

Hence, for each i ∈ S1 that sends one less transmission, there must exist one corresponding j ∈ S2 which sends one
more P
transmission. According
P to Lemma 7, if there exists such pair of (i, j), it must satisfy i < j and wi < wj . Let
P = i∈S1 (ri∗ − ri ) = j∈S2 (rj − rj∗ ) denote the total number of such pairs and P denote the partition of such pairs.
Therefore,
C(r) − C(r∗ ) =

N
X

wi ri −

i=0

=

X

N
X

wi ri∗

i=0
wi (ri − ri∗ )

X

X

wj (rj − rj∗ )

(57)

j∈S2

i∈S1

=

+

(56)

(wj − wi )

(58)

(i,j)∈P

≥0

(59)

Now, we are ready to prove Theorem 4.
Proof of Theorem 4. If there existsP
any linear coding scheme that achieves universal recovery by using K − d transmissions
with rate vector r = [r1 , . . . , rN ]T ( N
i=i ri = K − d), it is always possible to generate a corresponding linear coding scheme
based on (d, K)-Basis that have the same rate vectors [21]. Hence, they have the same weighted cost and we can only consider
∗ T
the coding schemes based on (d, K)-Basis. Let r∗ = [r1∗ , . . . , rN
] denote the rate vector output by Algorithm 3. According

18

to Lemma 7, there does not exist any i < j such that rj < rj∗ . Additionally, since S(r∗ ) = S(r), if rate vector r is different
from r∗ , the change can only be ∃i < j : ri < ri∗ and rj > rj∗ . According to Lemma 8, C(r) ≥ C(r∗ ). Therefore, the rate
vector output by Algorithm 3 has minimum weighted cost in all coding schemes which use K − d transmissions and achieve
universal recovery.
B. Proof of Theorem 5
In order to prove Theorem 5, we first prove two useful Lemmas.
Lemma 9. Let r(l) be the rate vector output by Algorithm 3 for input E and d = K − l. Thus, r(l) is the optimal rate
vector with minimum weighted cost among all the rate vectors with S(r) = l. For the coding schemes with rate vectors
r(l) = [r(l,1) , . . . , r(l,N ) ]T with l ∈ {Rmin , . . . , K} yielded by Algorithm 3,we have
(1) r(l+1,1) = r(l,1) + 1.
(2) r(l+1,m) ≤ r(l,m) + 1, ∀2 ≤ m ≤ N .
(3) If r(l+1,m) < r(l,m) , then r(l+2,m) ≤ r(l+1,m) .
Proof. (1) Since in Algorithm 3, we always start the generation of basis vectors from the PDV of node 1 and there is no
previously generated basis vector, then the number of basis vectors that should be generated by node 1 is
r(l,1) = wH (e1 ) − d = wH (e1 ) − K + l

(60)

Since Rmin ≤ l ≤ K and Rmin = K − min{M, d∗ }, we have 0 ≤ r(l,1) ≤ wH (e1 ). Note that wH (e1 ) ≥ M ≥ K − Rmin .
Therefore, for any feasible l, we have r(l+1,1) = r(l,1) + 1. This means the first node generates 1 more vector when the total
number of transmissions increases by 1. When r(l,1) = |X1 |, each transmissions is just a pure packet. In such cases, we have
d = 0 and l = K. Universal recovery can always be achieved when all packets have been sent individually. No coding scheme
with more than K transmissions should be considered.
(2) Similarly, for any 2 ≤ m ≤ N , the total number of feasible basis vectors that can be generated by node m is wH (em ) −
K + l. However, some of them may not be compatible with basis vectors that have been generated by previous nodes. Hence
we have
r(l,m) ≤ wH (em ) − K + l

(61)

And r(l+1,m) ≤ r(l,m) + 1, ∀2 ≤ m ≤ N . This means node m can generate at most 1 more basis vector when the total number
of transmissions increases by 1.
(3) As the total number of transmissions (sum rate) goes from l to l + 1, the corresponding basis changes from (K − l)-Basis
to (K − l − 1)-Basis. Therefore, the number of packets that are used to generate each transmission decreases by 1. Note that
wH (em ) ≥ M ≥ K − Rmin , ∀m ∈ [N ]. When l = Rmin , nodes m with wH (em ) = K − Rmin are not considered to
generate any basis vector, since every basis vector needs K − Rmin + 1 ones. But when l > Rmin , every node is considered
to generate basis vectors. If node i is not used to generate any basis vector, that means all basis vectors that can be generated
by node i are not compatible with the basis vectors generated by previous nodes. If r(l+1,m) < r(l,m) , that means besides
the first node, there exists at least one node with lower weight than node m that generates more basis vector(s), i.e. ∃n s.t.
n < m and r(l+1,n) > r(l,n) . The set of basis vectors that are generated to form (K − l − 1)-Basis by node m is a subset of
B(em , K − l). Let D(m, l + 1) denote vectors in B(em , K − l) but are not selected to form (K − l − 1)-Basis. Then every vector
in D(m, l + 1) is not compatible with (K − l − 1)-Basis vectors generated by priouves nodes. Any vector in B(em , K − l − 1)
which can be generated by vectors in D(m, l + 1) is also not compatible with (K − l − 2)-Basis vectors generated by priouves
nodes. Hence, the maximum number of basis vectors that can be generated by node m for next round is upperbounded by
r(l+1,m) . Therefore, If r(l+1,m) < r(l,m) , then r(l+2,m) ≤ r(l+1,m) , ∀2 ≤ m ≤ N .
Definition 8. Let S(l,↑) denote the set of nodes which generate more number of transmissions when the sum rate increases
from l to l + 1. Let S(l,0) denote the set of nodes which generate the same number of transmissions when the sum rate increases
from l to l + 1. Let S(l,↓) denote the multiset of nodes which generate fewer transmissions when the sum rate increases from
l to l + 1. The multiplicity of node i in S(l,↓) equals r(l,i) − r(l+1,i) .
i
Lemma 10. For ∀Rmin ≤ l ≤ K −1, we have (1) S(l+1,↑) ⊆ S(l,↑) and (2) Let Wl+1
be the ith largest w ∈ {wj : j ∈ S(l+1,↓) }
i
th
i
i
i
and Wl be the i largest w ∈ {wj : j ∈ S(l,↓) }. For any Wl+1 , there exists Wl such that Wl+1
≤ Wli .

Proof. Let r(l) = [r(l,1) , . . . , r(l,N ) ]T and r(l + 1) = [r(l,1) , . . . , r(l+1,N ) ]T denote the rate vectors output by Algorithm 3 for
d = K − l and d = K − l − 1, respectively. According to Theorem 4, r(l) and r(l) are optimal rate vectors for fixed sum rate
l and l + 1, respectively.
(1) Assuming that S(l+1,↑) 6⊆ S(l,↓) , then there must exist at least one node k, such that k ∈ S(l+1,↑) and k ∈
/ S(l,↑) . Hence,
k must be in S(l,0) or S(l,↓) . It is apparent that k 6= 1, since the first node always increases the rate by 1 when the total sum-rate
increases by 1. For k ∈ S(l+1,↑) \ {1}, there must always exist a corresponding node m ∈ S(l+1,↓) such that wk < wm .

19

(i) If k ∈ S(l,0) , we know that r(l+1,k) = r(l,k) . Coding scheme with rate vector r̂(l) = [r̂(l,1) , . . . , r̂(l,N ) ]T such that
r̂(l,k) = r(l+1,k) = r(l,k) + 1
r̂(l,m) = r(l+1,m) = r(l,m) − 1

(62)
(63)

r̂(l,i) = r(l,i) , ∀i ∈ [N ] \ {k, m}

(64)

can also achieve universal recovery. Moreover, coding scheme with rate vector r̂(l) has lower cost than coding scheme
with rate vector r(l). This contradicts that coding scheme with rate vector r(l) is optimal for all rate vector with sum
rate l.
(ii) If k ∈ S(l,↓) , we know that r(l+1,k) < r(l,k) . According to Lemma 9, r(l+1,k) ≤ r(l,k) . This contradicts our assumption
that k ∈ S(l+1,↑) .
Thus we have S(l+1,↑) ⊆ S(l,↑) .
1
(2)We use induction proof method to prove this part of lemma. For i = 1, let Wl+1
= wm , Wli = wn . We assume that
i
i
Wl+1 > Wl , then we have wm > wn which implies that m 6∈ S(l,↓) . Since S(l+1,↑) ⊆ S(l,↑) , coding scheme with rate vector
r̂(l) = [r̂(l,1) , . . . , r̂(l,N ) ]T which satisfies
r̂(l,m) = r(l,m) − 1
r̂(l,n) = r(l,n) + 1

(65)
(66)

r̂(l,j) = r(l,j) , ∀j ∈ [N ] \ {m, n}

(67)

can also achieve universal recovery with the same sum-rate and has lower weighted cost. This contradicts that coding scheme
1
≤ Wl1 . For
with rate vector r(l) = [r(l,1) , . . . , r(l,N ) ]T is optimal for all rate vector with sum rate l. Thus, we have Wl+1
i−1
i−1
i−1
i
i
i
i
i > 1, assuming that Wl+1 ≤ Wl , we show that Wl+1 ≤ Wl . let Wl+1 = wa , Wl = wb . If Wl+1 ≤ wb , then it is
i−1
i−1
i
straightforward that wa = Wl+1
≤ Wl+1
≤ wb = Wli . If Wl+1
> wb , and we assume that wa > wb . In such cases, a 6∈ S(l,↓) ,
i−1
i−1
since wa ≤ Wl+1 ≤ Wl . By using similar trick as we used for i = 1, it is able to show that there exist another coding
scheme which achieves universal recovery and has lower sum weighted cost. Hence the assumption wa > wb can never be
i
true. Therefore, Wl+1
≤ Wli .
Now we are ready to prove Theorem 5.
Proof of Theorem 5. For any Rmin ≤ l ≤ K − 2, we show that the second order difference of K(l) is non-negative, i.e.
F (l + 1) − F (l) ≥ 0, where F (l) = K(l + 1) − K(l). We compute the difference of the weighted cost of two coding schemes
when sum-rate increases by 1.
F (l + 1) = K(l + 2) − K(l + 1)
X
X
=
wi −
i∈S(l+1,↑)

= w1 +

(68)
wi

(69)

i∈S(l+1,↓)

X

wi −

i∈S(l+1,↑) \{1}

X

wi

(70)

i∈S(l+1,↓)

According to Lemma 9, node 1 always generates 1 more transmission when the total number of transmissions increases by 1.
And for other nodes, if their rate increases, the increment is 1, whereas if their rate decreases, the decrement can be more than
1. And the number of multiplications of the nodes in S(l+1,↓) is equal to the decrease in rate. Similarly, for sum-rate change
from l to l + 1, we have
X
X
wi −
F (l) = K(l + 1) − K(l) = w1 +
wi
(71)
i∈S(l,↑) \{1}

i∈S(l,↓)

The reason why node 1 is separated from other nodes is that the total number of transmissions only increases by 1, which
implies that the total number of transmissions sent by other nodes, except node 1, remains the same. Hence
|S(l,↑) \ {1}| = |S(l,↓) |

(72)

|S(l+1,↑) \ {1}| = |S(l+1,↓) |

(73)

Therefore, ∀i ∈ S(l,↑) \{1}, ∃j ∈ S(l,↓) such that wi < wj . We can construct a partition of node pairs (i, j), where i ∈ S(l,↑) \{1}
and j ∈ S(l,↓) as follows
P(l) = {(i, j) : i ∈ S(l,↑) \ {1}, j ∈ S(l,↓) , i < j}
(74)

20

Note that the number of node pairs in P(l) is equal to |S(l,↑) \ {1}|. Then we have
X
(wi − wj )
F (l) = w1 +

(75)

(i,j)∈P(l)

where every term of the summation (wi − wj ) is negative.
We show that for each pair (i, j) ∈ P(l + 1), there always exists a pair (î, ĵ) ∈ P(l) such that
wi − wj − (wî − wĵ ) ≥ 0

(76)

Assuming that there exists a node pair (i, j) ∈ P(l + 1) such that for all possible pairs (î, ĵ) ∈ P(l):
wi − wj − (wî − wĵ ) < 0

(77)

Equivalently, we have
wi − wj <

max
î∈S(l,↑) ,ĵ∈S(l,↓)

(wî − wĵ )

(78)

If i ∈ S(l,↑) , then wj > maxĵ∈S(l,↓) wĵ , which contradicts Lemma 10. If i 6∈ S(l,↑) , consider another coding scheme with rate
vector r = [r1 , r2 , . . . , rN ]T such that
ri = r(l+1,i) + 1, rj = r(l+1,j) − 1
rî = r(l+1,î) − 1, rĵ = r(l+1,ĵ) + 1

(79)
(80)

rm = r(l+1,m) , ∀m 6∈ {i, j, î, ĵ}

(81)

It can be verified that this coding scheme can also achieve universal recovery with total l + 1 transmissions. It has lower
weighted cost than the coding scheme with rate vector [r(l+1,1) , . . . , r(l+1,N ) ]T , which contradicts that coding scheme with
rate vector [r(l+1,1) , . . . , r(l+1,N ) ]T has the minimum weighted cost over all coding schemes that achieve universal recovery
with l + 1 transmissions. Starting form the node pair (i, j) with largest j, we can apply this binding for every (i, j) and remove
used (î, ĵ) iteratively. And it is able to find (î, ĵ) ∈ P(l) such that Eqn (76) is satisfied for every pair (i, j) ∈ P(l + 1). Hence,
we have
F (l + 1) − F (l)
X
(wi − wj ) −
=
(i,j)∈P(l+1)

X

=

X

(wm − wn )

(82)

(m,n)∈P(l)

[(wi − wj ) − (wî − wĵ )]

(i,j)∈P(l+1),(î,ĵ)∈P(l)

−

X

(wm − wn )

(83)

(m,n)∈P(l)\{Q}

≥0

(84)

where every (wi − wj ) − (wî − wĵ ) ≥ 0, every wm − wn < 0 and Q is the set of node pairs (î, ĵ) that are used in the first
P
summation. Hence, the function K(l) = minr∈Ω,S(r)=l N
i=1 wi ri is convex.
R EFERENCES

[1] S. El Rouayheb, A. Sprintson, and P. Sadeghi, “On coding for cooperative data exchange,” in Information Theory (ITW 2010, Cairo), 2010 IEEE
Information Theory Workshop on. IEEE, 2010, pp. 1–5.
[2] A. Sprintson, P. Sadeghi, G. Booker, and S. El Rouayheb, “A randomized algorithm and performance bounds for coded cooperative data exchange,” in
2010 IEEE International Symposium on Information Theory. IEEE, 2010, pp. 1888–1892.
[3] ——, “Deterministic algorithm for coded cooperative data exchange,” in International Conference on Heterogeneous Networking for Quality, Reliability,
Security and Robustness. Springer, 2010, pp. 282–289.
[4] N. Milosavljevic, S. Pawar, S. El Rouayheb, M. Gastpar, and K. Ramchandran, “Efficient algorithms for the data exchange problem,” IEEE Transactions
on Information Theory, vol. 62, no. 4, pp. 1878–1896, 2016.
[5] T. A. Courtade and R. D. Wesel, “Coded cooperative data exchange in multihop networks,” Information Theory, IEEE Transactions on, vol. 60, no. 2,
pp. 1136–1158, 2014.
[6] N. Ding, C. Chan, Q. Zhou, R. A. Kennedy, and P. Sadeghi, “Determining optimal rates for communication for omniscience,” IEEE Transactions on
Information Theory, vol. PP, no. 99, pp. 1–1, 2017.
[7] M. Gonen and M. Langberg, “Coded cooperative data exchange problem for general topologies,” Information Theory, IEEE Transactions on, vol. 61,
no. 10, pp. 5656–5669, 2015.
[8] A. Heidarzadeh, M. Yan, and A. Sprintson, “Cooperative data exchange with priority classes,” in 2016 IEEE International Symposium on Information
Theory (ISIT), July 2016, pp. 2324–2328.
[9] D. Ozgul and A. Sprintson, “An algorithm for cooperative data exchange with cost criterion,” in 2011 Information Theory and Applications Workshop,
Feb 2011, pp. 1–4.

21

[10] S. E. Tajbakhsh, P. Sadeghi, and R. Shams, “A generalized model for cost and fairness analysis in coded cooperative data exchange,” in Network Coding
(NetCod), 2011 International Symposium on. IEEE, 2011, pp. 1–6.
[11] A. Heidarzadeh and A. Sprintson, “Cooperative data exchange with unreliable clients,” in 2015 53rd Annual Allerton Conference on Communication,
Control, and Computing (Allerton), Sept 2015, pp. 496–503.
[12] I. Csiszar and P. Narayan, “Secrecy capacities for multiple terminals,” IEEE Transactions on Information Theory, vol. 50, no. 12, pp. 3047–3061, Dec
2004.
[13] H. Tyagi and S. Watanabe, “Universal multiparty data exchange and secret key agreement,” IEEE Transactions on Information Theory, vol. 63, no. 7,
pp. 4057–4074, July 2017.
[14] M. Yan and A. Sprintson, “Algorithms for weakly secure data exchange,” in 2013 International Symposium on Network Coding (NetCod). IEEE, 2013,
pp. 1–6.
[15] S. Jaggi, P. Sanders, P. A. Chou, M. Effros, S. Egner, K. Jain, and L. M. Tolhuizen, “Polynomial time algorithms for multicast network code construction,”
IEEE Transactions on Information Theory, vol. 51, no. 6, pp. 1973–1982, 2005.
[16] T. A. Courtade, B. Xie, and R. D. Wesel, “Optimal exchange of packets for universal recovery in broadcast networks,” in Military Communications
Conference, 2010-Milcom 2010. IEEE, 2010, pp. 2250–2255.
[17] R. Motwani and P. Raghavan, Randomized algorithms. Chapman & Hall/CRC, 2010.
[18] T. Ho, M. Médard, R. Koetter, D. R. Karger, M. Effros, J. Shi, and B. Leong, “A random linear network coding approach to multicast,” IEEE Transactions
on Information Theory, vol. 52, no. 10, pp. 4413–4430, 2006.
[19] S. H. Dau, W. Song, Z. Dong, and C. Yuen, “Balanced sparsest generator matrices for mds codes,” in Information Theory Proceedings (ISIT), 2013
IEEE International Symposium on. IEEE, 2013, pp. 1889–1893.
[20] N. J. A. Harvey, “Deterministic network coding by matrix completion,” Ph.D. dissertation, Massachusetts Institute of Technology, 2005.
[21] S. Li and M. Gastpar, “Cooperative data exchange based on MDS codes,” in 2017 IEEE International Symposium on Information Theory (ISIT)
(ISIT’2017), Aachen, Germany, Jun. 2017, pp. 1411–1415.
[22] A. Heidarzadeh and A. Sprintson, “Successive local and successive global omniscience,” in 2017 IEEE International Symposium on Information Theory
(ISIT), June 2017, pp. 2313–2317.

