IEEE TRANSACTIONS ON INFORMATION THEORY

1

Determining Optimal Rates for Communication for
Omniscience

arXiv:1611.08367v3 [cs.IT] 1 Oct 2017

Ni Ding, Chung Chan, Qiaoqiao Zhou, Member, IEEE, Rodney A. Kennedy, Fellow, IEEE and
Parastoo Sadeghi, Senior Member, IEEE

Abstract—This paper considers the communication for omniscience (CO) problem: A set of users observe a discrete
memoryless multiple source and want to recover the entire
multiple source via noise-free broadcast communications. We
study the problem of how to determine an optimal rate vector
that attains omniscience with the minimum sum-rate, the total
number of communications. The results cover both asymptotic
and non-asymptotic models where the transmission rates are real
and integral, respectively. We propose a modified decomposition
algorithm (MDA) and a sum-rate increment algorithm (SIA) for
the asymptotic and non-asymptotic models, respectively, both
of which determine the value of the minimum sum-rate and
a corresponding optimal rate vector in polynomial time. For the
coordinate saturation capacity (CoordSatCap) algorithm, a nesting algorithm in MDA and SIA, we propose to implement it by a
fusion method and show by experimental results that this fusion
method contributes to a reduction in computation complexity.
Finally, we show that the separable convex minimization problem
over the optimal rate vector set in the asymptotic model can be
decomposed by the fundamental partition, the optimal partition
of the user set that determines the minimum sum-rate, so that
the problem can be solved more efficiently.
Index Terms—communication for omniscience, Dilworth truncation, mutual dependence, submodularity.

I.

INTRODUCTION

Assume that there are a finite number of users in a system.
Each of them observes a distinct component of a discrete
multiple correlated source in private. The users are allowed to
exchange their observations over public authenticated broadcast channels. We assume that these channels are noiseless
so that all the transmissions are correctly heard, or received,
by all users. The communications could be interactive and
the rates of public communications are unconstrained. That is,
there are no capacity upper bounds imposed on the broadcast
links. The purpose is to attain omniscience, the state that
each user obtains all the components in the entire multiple
The primary results have been published in [1]. Part of the results have
also been published in [2], [3].
Ni Ding, Rodney A. Kennedy and Parastoo Sadeghi are with the Research
School of Engineering, the Australian National University (email: {ni.ding,
rodney.kennedy, parastoo.sadeghi}@anu.edu.au). Part of the work of Ni Ding
(email: ni.ding@inc.cuhk.edu.hk) has been done when she was a junior
research assistant at the Institute of Network Coding, The Chinese University
of Hong Kong, from Nov 23, 2015 to Feb 6, 2016.
Chung Chan (email: cchan@inc.cuhk.edu.hk) and Qiaoqiao Zhou (email:
zq115@ie.cuhk.edu.hk) are with the Institute of Network Coding, The Chinese
University of Hong Kong.
Chung Chan was supported in part by the Vice-Chancellors One-off
Discretionary Fund of The Chinese University of Hong Kong under Project
VCF2014030 and Project VCF2015007 and in part by the University Grants
Committee of the Hong Kong Special Administrative Region, China, under
Project 14200714.

source in the system. This problem is called communication
for omniscience (CO), which was originally formulated in [4].
The CO problem in [4] is based on an asymptotic model where
the length of the observation sequence is allowed to approach
infinity. Whereas the authors in [5]–[7] also study the nonasymptotic model where the number of observations is finite
and the communication rates are restricted to be integral. In
fact, the non-asymptotic model is important in a practical
problem in peer-to-peer (P2P) wireless communications as
described below.
The finite linear source model studied in [6] is an example of
the non-asymptotic model, where the multiple random source
is represented by a vector that belongs to a finite field and
the users transmit linear combinations of their observations to
obtain this vector. By assuming that each dimension in this
vector represents a packet, the finite linear source model can
describe the situation when a base station wants to disseminate
a set of packets to a group of mobile clients: Each client
only obtains a partial knowledge of the packet set due to the
fading effects of the wireless channels. The omniscience of the
packet set can be attained by letting the clients transmit linear
combinations of packets, say, by some network coding scheme,
e.g., [8], via the P2P channels, which could be more reliable
than the retransmissions over base-to-peer (B2P) channels if
the clients are geographically close to each other. The CO
problem in this packet model is called coded cooperative data
exchange (CCDE) which was independently proposed in [8]–
[10] and further studied in [11]–[15]. In [15], [16], the idea
of packet-splitting was introduced to CCDE. It allows each
packet to be divided into a number of chunks so that the
transmissions in CCDE refer to the linear combinations of
chunks and the normalized transmission rates are fractional.
This can be considered as an extension of the CCDE and finite
linear source model towards the asymptotic model.
An optimization problem that naturally arises is how to
attain omniscience with the least cost and the cost usually
refers to the overall transmission rates, or sum-rate, e.g.,
the total number of linear combinations of packets that are
transmitted by all clients in CCDE. It is shown in [4] that
the Slepian-Wolf (SW) constraints [17] on all proper subsets
of the user set determine the omniscience-achievability of a
transmission rate vector. Hence, in [4], [7], [9], [10], [14],
[15], [18]–[20], the problem of minimizing the sum-rate is
formulated by linear programming (LP) and the combinatorial
nature of this problem has also been revealed. Then, instead
of solving the minimum sum-rate problem directly by the
existing LP algorithms, the main issue is how to deal with

2

the exponentially growing number of constraints.
In the studies on the finite linear source model in [18],
[21] and CCDE in [2], [3], [9], [10], [14], [15], [22], [23],
the submodularity of the minimum sum-rate problem was
revealed, which is essentially due to the submodularity of
the entropy function.1 In particular, it is shown in [2], [3],
[21], [22] that, in a non-asymptotic model where the entropy
function takes integer values,2 all omniscience-achievable rate
vectors that have the same sum-rate constitute a submodular
base polyhedron. Since a rate vector in this submodular base
polyhedron can be found by the Edmond greedy algorithm3
and the variation range of the minimum sum-rate in a nonasymptotic model is integral and bounded,4 the minimum sumrate and a corresponding optimal rate vector are determined
efficiently by the sum-rate adaption algorithms proposed in
[15], [18]. However, it still remains unclear if all the results
derived in [2], [3], [21], [22] for the non-asymptotic model also
hold for the asymptotic one and if there exists an algorithm
that can efficiently determine an optimal rate vector that
attains omniscience by the minimum sum-rate in an asymptotic
model where the variation range of the minimum sum-rate is
continuous. On the other hand, the study in [16] shows that
allowing packet-splitting in CCDE incurs less transmission
costs in P2P communications. It could mean that the minimum
sum-rate in the asymptotic model is no greater than the one in
the non-asymptotic model in the same system, which makes
it desirable to know the optimal solution for CO in the
asymptotic model.
The importance of studying the CO problem is also highlighted by its dual relationship with the secret capacity, the
maximum rate at which the secret key can be generated by the
users in the system, in [4]: The secret capacity equals to the
total amount of information in the multiple source subtracted
by the minimum sum-rate (in an asymptotic model) for them
to achieve omniscience. It is also pointed out in [4] that the
secret capacity is upper bounded by a mutual dependence over
the partitions of the users and this upper bound is shown to be
tight in [27].5 The mutual dependence is also named as shared
information in [28] for the secret generation problem and
multivariate mutual information (MMI) in [19], [20], where
the authors in [19] proposed this mutual dependence to be the
generalization of Shannon’s mutual information for multiple
1 In [24, Section 3], it is shown that the entropy function is the rank function
of a polymatroid, which belongs to a subgroup of submodular functions. The
entropy function reduces to the matrix rank function in the finite linear source
model and the cardinality function in CCDE, both of which are submodular.
2 Finite linear source model and CCDE are examples of non-asymptotic
model with integer-valued entropy function.
3 The Edmond greedy algorithm in [25] is a special case of the coordinate
saturation capacity algorithm [26, Greedy Algorithm II in Section 3.2] for
normalized submodular functions [26, Theorems 3.18 and 3.19]. The one
implemented in [15], [18] is modified for the crossing and intersecting
submodular functions, respectively.
4 The value of the minimum sum-rate is real in the asymptotic model and
integral in the non-asymptotic model. It is nonnegative and no greater than
the total amount of information in the multiple source.
5 The authors in [4] derived the results on secret capacity in a general
setting: A subset of the users are active while the others are the helpers that
assist the active users in generating the secret key. The author in [27] proved
that the upper bound on secret capacity is tight when there is no helpers, i.e.,
all the users in the system are active.

IEEE TRANSACTIONS ON INFORMATION THEORY

random variables. Then, determining secret capacity, mutual
dependence, shared information or MMI relies on the solution
to the CO problem in the asymptotic model and vice versa.
It is shown in [19] that the problem of obtaining the MMI
reduces to the task of determining the value of the Dilworth
truncation, which can be solved in strongly polynomial time
due to the submodularity of the entropy function. However,
for solving the CO problem, knowing the minimum sum-rate
is not sufficient: We also need to know how to distribute the
minimum sum-rate among the users so that omniscience is
achievable. Therefore, it is required to determine an optimal
rate vector that attains omniscience with the minimum sumrate.
The work in this paper is based on the CO problem that is
originally formulated in [4]. We consider the minimum sumrate problem: how to attain omniscience with the minimum
total number of communications. The work in this paper
differs form [4], [27], [28] in that, in addition to characterizing
the minimum sum-rate or discussing how to obtain the value
of it, we are particularly interested in how to determine a
corresponding optimal rate vector that attains omniscience.
The results cover both asymptotic and non-asymptotic models.
For the non-asymptotic model, we focus on the finite linear
source model and CCDE. For solving the CO problem, we
propose a modified decomposition algorithm (MDA) and a
sum-rate increment algorithm (SIA) for the asymptotic and
non-asymptotic models, respectively, both of which determine
the value of the minimum sum-rate and a corresponding
optimal rate vector in polynomial time. For the coordinate saturation capacity (CoordSatCap) algorithm, a nesting algorithm
in the MDA and SIA algorithm, we propose to implement it
by a fusion method and show by experimental results that
this fusion method contributes to a reduction in computation
complexity as compared to the CoorSatCap algorithm that
is implemented in [15], [18]. We also derive results on the
fundamental partition P ∗ , the finest optimal partition of the
user set that determines the value of the minimum sum-rate in
the asymptotic model,6 which is also determined by the MDA
algorithm. It is shown that, in CCDE, the omniscience of a
packet set can be attained by splitting each packet into |P ∗ |−1
chunks. Finally, we reveal some decomposition properties of
P ∗ . We show that the separable convex minimization problem
over the optimal rate vector set in the asymptotic model can
be decomposed by P ∗ so that the problem can be solved more
efficiently.
A. Summary of Main Results
Our main results are summarized as follows.
1) We show that all omniscience-achievable rate vectors
with the sum-rate equal to a given value form a base polyhedron. By observing the nonemptiness of the base polyhedron, we prove directly based on [26, Theorems 2.5(i) and
2.6(i)] that the minimum sum-rate in the asymptotic model is
6 It is shown in [19] that the optimal partitions that give rise to the minimum
sum-rate form a Dilworth truncation lattice [29] where the minimal/finest and
maximal/coarsest minimizers exist. The name ‘fundamental partition’ was first
used in [19] to denote the finest partition in this lattice.

DING et al.: DETERMINING OPTIMAL RATES FOR COMMUNICATION FOR OMNISCIENCE

determined by an optimization over the partitions of the user
set. This result verifies the proof in [27] on the tightness of
the lower bound on the minimum sum-rate for CO that was
proposed in [4]. For the non-asymptotic model, we show that
the minimum sum-rate is the least integer that is no less than
the one in the asymptotic model, which provides theoretical
proof to an observation in [15]: The difference in minimum
sum-rate between the asymptotic and non-asymptotic models
is no greater than one. Since the optimal rate vectors also
form a base polyhedron, we use the integrality of the extreme
points in this base polyhedron to show two results for the
minimum sum-rate problem in the finite linear source model,
or CCDE: (a) there exists an integral optimal rate vector, which
is consistent with the results in [15], [18], and (b) there exists
a fractional optimal rate vector that can be implemented by
dividing each packet into |P ∗ | − 1 chunks.
2) For determining an optimal rate vector in the asymptotic
model, an MDA algorithm is proposed. It starts with a lower
estimation on the minimum sum-rate and iteratively updates
it by the finest minimizer of a Dilworth truncation problem
until the minimum is reached and a corresponding optimal rate
vector is determined. For the CoordSatCap algorithm, which
is originally proposed in [26, Greedy Algorithm II in Section
3.2], for solving the Dilworth truncation problem in each
iteration of the MDA algorithm, we propose a fusion method
implementation (CoordSatCapFus) so that the submodular
function minimization (SFM) in each iteration is solved over
a merged or fused user set with the cardinality no greater than
the original one. We show that the optimal solution returned
by the MDA algorithm for the asymptotic model can also be
utilized for solving the minimum sum-rate problem in the nonasymptotic model by no more than one additional call of the
CoordSatCapFus algorithm. Independently, we also propose an
SIA algorithm for determining an optimal rate vector as well
as the minimum sum-rate for the non-asymptotic model. Both
the MDA and SIA algorithms complete in polynomial time
based on the existing SFM techniques. We run experiments
to show that the fusion method CoordSatCapFus contributes
to a reduction in computation complexity as compared to the
CoorSatCap algorithm, which is implemented in [15], [18] for
the finite linear source model, and the reduction is considerable
when the number of users grows.
3) For the initial estimations in the MDA and SIA algorithms, we derive a lower bound (LB) on the minimum sumrate for both asymptotic and non-asymptotic models that can
be determined in linear time. We show that this lower bound
can be used as the initial estimation of the minimum sumrate searching algorithms, e.g., the MDA and SIA algorithm
proposed in this paper for the asymptotic and non-asymptotic
models, respectively. The observation that a lower bound can
initiate the minimum sum-rate searching algorithm is also
consistent with the results in [15], [18] for the finite linear
source model.7 We run experiments to show that the proposed
7 For the finite linear source model, or CCDE, it is suggested in [15,
Appendix F] to adapt the sum-rate from either lower or upper bound to the
minimum, while [18, Algorithms 3] is a binary search method starting with
the initial lower and upper bounds on the minimum sum-rate.

3

LB in the non-asymptotic model is much tighter than the ones
in [8], [11].
4) We also study the minimum weighted sum-rate problem
in the optimal rate vector set, a problem that was originally
formulated and studied for the finite linear source model in
[15], [18]. It is shown that by choosing a proper linear ordering
of the user indices the optimal rate vectors returned by the
MDA and SIA algorithms also minimize a weighted sum-rate
function in the optimal rate vector set for the asymptotic and
non-asymptotic models, respectively. The result that the minimum weighted sum-rate problem can be solved by a proper
linear ordering for the non-asymptotic model is consistent with
the results in [15], [18]. Our study shows that this idea can
also be applied to the asymptotic model.
5) We show that the fundamental partition P ∗ is the minimal
separator of a submodular function which gives rise to the
decomposition property of P ∗ in the asymptotic model: The
separable convex function minimization problem over the
optimal rate vector set can be broken into |P ∗ | subproblems, each of which formulates the separable convex function
minimization problem in one element or user subset in P ∗ .
These subproblems can be solved separately so that the overall
complexity is reduced.
B. Organization
In Section II, we present the system model for CO and
describe the asymptotic and non-asymptotic models, the finite
linear source model and CCDE. In Section III, we analyze
the minimum sum-rate problem in both asymptotic and nonasymptotic models based on the concepts of submodularity
and Dilworth truncation. In Section IV, a LB on the minimum
sum-rate is proposed for the asymptotic and non-asymptotic
models, which is used in Section V to initiate the MDA
and SIA algorithms. The complexity of both algorithms is
also discussed in Section V. In Section VII, we reveal the
decomposition property of the fundamental partition in the
asymptotic model.
II. S YSTEM M ODEL
Let V with |V | > 1 be a finite set that contains the
indices of all users in the system. We call V the ground set.
Let ZV = (Zi : i ∈ V ) be a vector of discrete random
variables indexed by V . For each i ∈ V , user i privately
observes an n-sequence Zni of the random source Zi that is
i.i.d. generated according to the joint distribution PZV . We
allow users exchange their sources directly so as to let all
users in V recover the source sequence ZnV . The state that each
user obtains the total information in the entire multiple source
is called omniscience, and the process that users communicate
with each other to attain omniscience is called communication
for omniscience (CO) [4].
Let rV = (ri : i ∈ V ) be a rate vector indexed by V . We
call rV an achievable rate vector if the omniscience can be
attained by letting users communicate with the rates designated
by rV . Let r be the sum-rate function associated with rV such
that
X
r(X) =
ri , ∀X ⊆ V
i∈X

4

IEEE TRANSACTIONS ON INFORMATION THEORY

with the convention that r(∅) = 0. r(V ) is the sum-rate of
rV over all users, or the total number of transmissions, in
the system. For X, Y ⊆ V , let H(ZX ) be the amount of
randomness in ZX measured by Shannon entropy [30] and
H(ZX |ZY ) = H(ZX∪Y ) − H(ZY ) be the conditional entropy
of ZX given ZY . In the rest of this paper, without loss of
generality, we simplify the notation ZX by X.
It is shown in [4] that an achievable rate vector must satisfy
the Slepian-Wolf (SW) constraints [17]:
r(X) ≥ H(X|V \ X),

∀X ( V.

(1)

The interpretation of (1) is: To attain omniscience, the total
amount of information sent from user set X should be at least
equal to the total amount of information that is missing in
V \ X. The set of all achievable rate vectors is [4]8
RCO (V ) = {rV ∈ R|V | : r(X) ≥ H(X|V \ X), ∀X ( V }.
We say that α is an achievable sum-rate if there exists an
achievable rate vector rV ∈ RCO (V ) such that r(V ) = α.

A. Asymptotic and Non-asymptotic Models
We consider both asymptotic and non-asymptotic models.
In the asymptotic multiple random source model, we will
study the CO problem by considering the asymptotic limits
as the block length n goes to infinity. The communication
rates in an asymptotic model could be real or fractional. The
minimum sum-rate can be determined by the following linear
programming (LP) [4, Proposition 1]
RACO (V ) = min{r(V ) : rV ∈ RCO (V )}

(2)

and the set of all optimal rate vectors is
∗
RACO
(V ) = {rV ∈ RCO (V ) : r(V ) = RACO (V )}.

In the non-asymptotic model, the block length n is finite
and the communication rates are required to be integral. The
minimum sum-rate can be determined by the integer linear
programming (ILP) [14], [15], [18]9
RNCO (V ) = min{r(V ) : rV ∈ RCO (V ) ∩ Z|V | }

(3)

and the optimal rate vector set is
∗
RNCO
(V ) = {rV ∈ RCO (V ) ∩ Z|V | : r(V ) = RNCO (V )}.

The non-asymptotic model is exemplified by the finite linear
source model and CCDE as explained as follows.
8 The achievable rate region was originally given in [4] based on the SW
constrains in a more general case: The omniscience problem in the active user
set A ⊆ V with the users in V \ A serving as the helpers. The CO problem
studied in this paper is the case when A = V .
9 This ILP problem has been formulated in [14], [15] in terms of the
cardinality function for CCDE and in [18] in terms of the rank function for
the finite linear source model.

B. Finite Linear Source Model and CCDE
Let Fq be a finite field. q is the order of Fq such that q = pN ,
where p is a prime number and N is a positive integer. In a
finite linear multiple source model, we assume that each Zi
can be expressed by an l(zi )-dimensional column vector zi in
l(z )
the finite field Fq i such that
zi = Ai x,
l(x)

where x ∈ Fq is some l(x)-dimensional uniformly disl(z )×l(x)
tributed random vector and Ai ∈ Fq i
is an l(zi )-byl(x) matrix. For X ⊆ V , let AX = [Ai : i ∈ X]. In the
finite linear source model, the value of the entropy function
at X reduces to the rank of AX , i.e., H(X) = rank(AX ) and
H(X|Y ) = rank(AX∪Y ) − rank(AY ). Then, H is integervalued, i.e., H(X) ∈ Z+ , ∀X ⊆ V , and we assume that
H(V ) = l(x). The users transmit linear combinations of
zi s in order to attain the omniscience of x.10 Therefore, the
finite linear source model is an example of the non-asymptotic
model where the value of the entropy function H is integral.
By realizing that each dimension in x can represent a packet,
the finite linear source model poses a practical problem in
wireless communications: the omniscience, or recovery, of a
packet set in peer-to-peer (P2P) wireless network. Let all the
users in V be mobile clients that are geographically close
to each other so that any client’s broadcasts can be received
losslessly by the others. Consider the problem of disseminating
the packet set x from a base station to all mobile clients in
V . Due to the fading effects of wireless channels, each client
may just obtain a partial knowledge of x at the end of base-topeer (B2P) transmissions, but the clients’ knowledge could be
complementary to each other. In this case, we can set free the
base station and let the clients transmit linear combinations of
packets, e.g., by some network coding scheme [8], so as to help
each other recover x. The omniscience problem in this packet
model is how to let all users recover the packet set x with the
least number of transmissions and this problem, which was
originally formulated in [8], is called the coded cooperative
data exchange (CCDE). The concept of packet-splitting was
also introduced to CCDE in [15], [16]. It extends the finite
linear source model from a non-asymptotic setting towards an
asymptotic one, which is explained by the following example.
Example II.1. There are three users V = {1, 2, 3} in the
system. They observe respectively
Z1 = (Wa , Wb , Wc , Wd , We ),
Z2 = (Wa , Wb , Wf ),
Z3 = (Wc , Wd , Wf ),
where each Wj is an independent uniformly distributed random bit. The purpose is to let all the users attain the
omniscience of ZV via communications. In the corresponding
CCDE system (see Fig. 1), each Wj represents a packet so that
the column vector zi denotes all the packets received by mobile
client i after the B2P transmissions. All mobile clients in V
10 In a finite linear source model, it is sufficient for the user i to transmit
linear combinations of zi s to attain omniscience [6].

DING et al.: DETERMINING OPTIMAL RATES FOR COMMUNICATION FOR OMNISCIENCE

client 3
z3 = [Wc , Wd , Wf ]⊺

client 1

client 2

z1 = [Wa , Wb , Wc , Wd , We ]

⊺

z2 = [Wa , Wb , Wf ]⊺

Fig. 1. The corresponding CCDE system for the CO problem in Example II.1,
where Wj denotes a packet that belongs to a field Fq . There are three clients
that want to obtain six packets in x = [Wa , . . . , Wf ]⊺ . User i initially
obtains zi . The users transmit linear combinations of zi s via lossless wireless
broadcast channels to help the others recover all packets in x.

transmit linear combinations of zi s over P2P channels in other
to attain the omniscience of all packets in x = [Wa , . . . , Wf ]⊺ .
In this system, we have all the achievable rate vectors
contained in

RCO (V ) = rV ∈ R|V | : r(∅) = 0,
r({1}) ≥ H({1}|{2, 3}) = 1,
r({2}) ≥ H({2}|{1, 3}) = 0,

r({3}) ≥ H({3}|{1, 2}) = 0,
r({1, 2}) ≥ H({1, 2}|{3}) = 3,
r({1, 3}) ≥ H({1, 3}|{2}) = 3,
r({2, 3}) ≥ H({2, 3}|{1}) = 1 .
One can show that the minimum sum-rate is RACO (V ) = 72
∗
and the optimal rate vector set is RACO
(V ) = {( 25 , 12 , 21 )}
for the asymptotic model. In CCDE, the rate vector ( 52 , 12 , 12 )
can be implemented by packet-splitting. Let the users divide
each packets into two chunks of equal length, e.g., z2 =
(1)
(2)
(1)
(2)
(1)
(2)
(Wa , Wa , Wb , Wb , Wf , Wf ) where each Wj is split
(2)
(1)
to Wj and Wj . Let the users transmit the rate (5, 1, 1)
with each tuple denoting the number of linear combinations of the packet chunks. We have ( 52 , 12 , 21 ) and 27 being
the normalized rate vector and sum-rate, respectively. For
the non-asymptotic model, we have the minimum sum-rate
∗
RNCO (V ) = 4 and the optimal rate vector set RNCO
(V ) =
{(3, 0, 1), (2, 1, 1), (3, 1, 0)}.
We show an example of how to implement the rate vector
∗
(2, 1, 1) in RNCO
(V ) for the non-asymptotic model by a
network coding scheme. The implementation of other optimal
∗
∗
(V ) can
rate vectors in RNCO
(V ) and ( 52 , 12 , 21 ) in RACO
be derived in a similar manner. By letting user 1 transmit
Wb + Wf + Wc and We , user 2 transmit Wa + Wf and user 3
transmit Wd + Wf , all the users are able to recover the whole
packet set x. For example, user 2 receives We , recovers Wc by
subtracting message Wb +Wf +Wc by Wb +Wf and recovers
Wd by subtracting message Wd + Wf by Wf so that he/she
obtains all the packets in x. The corresponding transmission
rate vector in this coding scheme is (2, 1, 1).11
For a fractional rate vector rV , let k ∈ Z+ be the least
common multiple (LCM) of all denominators of ri s, i.e., k is
11 The coding scheme that implements an achievable rate vector r
V is not
necessarily unique.

5

the minimum nonnegative integer such that krV = (kri : i ∈
V ) is integral. It means that rV can be implemented by kpacket-splitting, i.e., dividing each packet into k chunks, in
CCDE. For example, in Example II.1, k = 2 is the LCM
of the denominators of all dimensions in rV = ( 52 , 12 , 12 ),
which means ( 25 , 12 , 12 ) can be implemented by 2-packetsplitting. Therefore, in CCDE, we are not only interested in
∗
the existence of an integral optimal rate vector in RNCO
(V )
for the non-asymptotic setting, but are also concerned whether
∗
there exists a fractional optimal rate vector in RACO
(V ) for
the asymptotic setting and how large is the LCM k.
III. M INIMUM

SUM - RATE AND

O PTIMAL R ATE V ECTOR

The fundamental problem in CO is how to obtain the value
of the minimum sum-rate and an optimal rate vector: the value
∗
of RACO (V ) and a rate vector in RACO
(V ) for the asymptotic
∗
model and the value of RNCO (V ) and a rate vector in RNCO
(V )
for the non-asymptotic model. Although the minimum sumrate problem can be formulated by LP (2) and ILP (3) for
asymptotic and non-asymptotic settings, respectively, it is
not efficient to directly solve them since the number of the
constraints grow exponentially in |V |. In this section, we reveal
the equivalence between the constant sum-rate achievable
rate region and a base polyhedron. Directly based on the
nonemptiness of this based polyhedron, we show that the
minimum sum-rate in the asymptotic model is determined by
an optimization problem over the partitions of the user set,
which revisits the results in [4], [27]. We also show that the
minimum sum-rate in the non-asymptotic model is the least
integer that is no less than the one in the asymptotic model.
A. Preliminaries
We first describe submodularity and the related concepts as
follows. For a set function f : 2V 7→ R, the polyhedron and
base polyhedron of f are respectively [26, Section 2.3] [31,
Definition 9.7.1]
P (f, ≤) = {rV ∈ R|V | : r(X) ≤ f (X), ∀X ⊆ V },
B(f, ≤) = {rV ∈ P (f, ≤) : r(V ) = f (V )}.
In the same way, we can define P (f, ≥) and B(f, ≥). A set
function f is submodular if the submodular inequality
f (X) + f (Y ) ≥ f (X ∩ Y ) + f (X ∪ Y )

(4)

holds for all X, Y ⊆ V ; f is supermodular if −f is submodular; f is modular if it is both submodular and supermodular
[26, Section 2.3]. P (f, ≤) and B(f, ≤) are submodular polyhedron and base polyhedron, respectively, if f is submodular.
A set function f is intersecting submodular if the submodular
inequality (4) holds for all sets that are intersecting, i.e., all
X, Y ⊆ V such that X ∩ Y 6= ∅ [26, Section 2.3]. Note, an
intersecting submodular function f may or may not require (4)
hold for all X, Y ⊆ V , which means a submodular function
is also intersecting submodular, but not necessarily vice versa.
A set function f is the rank function of a polymatroid if
it is (a) normalized: f (∅) = 0; (b) monotonic: f (X) ≥ f (Y )
for all X, Y ⊆ V such that Y ⊆ X; (c) submodular [26,
Section 2.2]. If f is a polymatroid rank function, the normality

6

IEEE TRANSACTIONS ON INFORMATION THEORY

r(V ) = 16
5
#
, ≤)
P (f16/5

r3

1

r3

1

r(V ) = 27
#
∗
, ≤)
RACO
(V ) = B(f7/2
#
, ≤)
P (f7/2

0

0
1

r2

0 0

1

3

2

4

1

r2

r1

, the polyhedron
Fig. 2. For the system in Example II.1, when α = 16
5
#
P (f16/5
, ≤) does not intersect with the plane {rV ∈ R3 : r(V ) = 16
}.
5

0 0

1

3

2

4

r1

Fig. 3. For the system in Example II.1, when α = 27 , the the polyhe#
dron P (f7/2
, ≤) intersects with the plane {rV ∈ R3 : r(V ) = 27 } at

#
Therefore, B(f16/5
, ≤) = {rV ∈ RCO (V ) : r(V ) = 16
} = ∅. It means
5
16
that sum-rate 5 is not achievable or there does not exist an achievable rate
vector that has sum-rate equal to 16
.
5

#
rV = ( 25 , 12 , 21 ), i.e., B(f7/2
, ≤) = {rV ∈ RCO (V ) : r(V ) = 72 } =
5 1 1
{( 2 , 2 , 2 )}. In this case, sum–rate 27 is achievable and there is only one
optimal rate vector for the asymptotic model.

and monotonicity ensure the nonnegativity of f , i.e., f (X) ≥
|V |
0, ∀X ⊆ V , and B(f, ≤) ⊆ R+ [26, Lemma 3.23]. It is
shown in [24, Section 3] that the entropy function H is a
polymatroid rank function. It is easy to see that r, the sum-rate
function that is associated with a rate vector rV , is modular
and f (X) − r(X) is submodular/intersecting submodular if f
is submodular/intersecting submodular.

described by B(fα# , ≤). It is obvious that B(fα# , ≤) 6= ∅
if the polyhedron P (fα# , ≤) intersects with the hyperplane
{rV ∈ R|V | : r(V ) = α}. Also, the optimal rate sets can
be described by the base polyhedra

B. Nonemptiness of the Base Polyhedron
For α ∈ R+ , we define
(
H(X|V \ X) X ( V
fα (X) =
.
α
X=V
The base polyhedron of fα
B(fα , ≥) = {rV ∈ P (fα , ≥) : r(V ) = fα (V )}
= {rV ∈ RCO (V ) : r(V ) = α}
contains all achievable rate vectors that have sum-rate equal
to α. It is possible that B(fα , ≥) = ∅, which means that the
sum-rate α is not achievable. Let fα# be the dual set function
of fα that is defined as [26, Section 2.3]
fα# (X) = fα (V ) − fα (V \ X)
= α − fα (V \ X),

∀X ⊆ V.

Consider the constraint r(X) ≥ fα (X) in B(fα , ≥). If we
restrict the rate vector rV to satisfy r(X) ≥ fα (X) for some
X ⊆ V and r(V ) = α, then we necessarily put constraint
r(V \ X) = r(V ) − r(X) ≤ α − fα (V \ X) = fα# (V \ X)
on set V \ X. By converting the constraints in B(fα , ≥) in
the same way for all X ⊆ V , we get the base polyhedron
B(fα# , ≤) = {rV ∈ P (fα# , ≤) : r(V ) = fα# (V ) = α}
such that B(fα# , ≤) = B(fα , ≥) [26, Lemma 2.4].12 Then,
the set of all achievable rate vectors with sum-rate α is
[26, Lemma 2.4], B(fα# , ≤) = B(fα , ≥) holds without the submodularity or intersecting submodularity of fα# .
12 In

∗
RACO
(V ) = B(fR#ACO (V ) , ≤);
∗
RNCO
(V ) = B(fR#NCO (V ) , ≤) ∩ Z|V | .

Therefore, the minimum sum-rate, either RACO (V ) or
RNCO (V ), can be determined by studying the condition on
α for the nonemptiness of B(fα# , ≤), and a rate vector in
∗
∗
the optimal rate set, either RACO
(V ) or RNCO
(V ), can be
determined by any algorithm that is able to search a base point
rV in B(fR#ACO (V ) , ≤) or B(fR#NCO (V ) , ≤) ∩ Z|V | .13
Example III.1. For the system in Example II.1, we have
B(fα , ≥) = {r ∈ RCO (V ) : r(V ) = α}. For a fixed value of
α, consider the constraint r({1}) ≥ fα ({1}) = 1 in B(fα , ≥).
Since we restrict the sum-rate to be r({1, 2, 3}) = α, we
have constraint r({2, 3}) = α − r({1}) ≤ α − fα ({1}) =
fα# ({2, 3}) = α − 1. If we convert the constraints one by one
in B(fα , ≥), we have the dual base polyhedron

B(fα# , ≤) = rV ∈ R|V | : r(∅) = 0, r({1}) ≤ α − 1,
r({2}) ≤ α − 3, r({3}) ≤ α − 3,
r({1, 2}) ≤ α, r({1, 3}) ≤ α,
r({2, 3}) ≤ α − 1,
r({1, 2, 3}) = α
such that B(fα# , ≤) = B(fα , ≥). We increase the value of α
from 0. It can be shown that B(fα# , ≤) = ∅ when α < 72 , e.g.,
7
∗
when α = 16
5 in Fig. 2. When α = 2 , we have RACO (V ) =
#
5 1 1
B(f7/2 , ≤) = {( 2 , 2 , 2 )} as in Fig. 3. We keep increasing α
after reaching 72 . It can be shown that B(fα# , ≤) ∩ Z|V | = ∅
∗
when α < 4. When α = 4, we have RNCO
(V ) = B(f4# , ≤
|V |
) ∩ Z = {(3, 0, 1), (2, 1, 1, ), (3, 1, 0)} as shown in Fig. 4.
13 A base (point) is a |V |-dimension vector r
V in B(f, ≤), where f is a
set function defined on the power set 2V .

DING et al.: DETERMINING OPTIMAL RATES FOR COMMUNICATION FOR OMNISCIENCE

r(V ) = 4
B(f4# , ≤)
P (f4# , ≤)
∗
RNCO
(V ) = B(f4# , ≤) ∩ Z3

r3

1

r2

1

0 0

4

3

2

r1

Fig. 4. For the system in Example II.1, when α = 4, the polyhedron
P (f4# , ≤) and the plane {rV ∈ R3 : r(V ) = 4} intersect, i.e., B(f4# , ≤) =
∗ (V ) = B(f # , ≤) ∩ Z3 =
{rV ∈ RCO (V ) : r(V ) = 4} 6= ∅. Also, RNCO
4
{(2, 1, 1), (3, 0, 1), (3, 1, 0)}. In this case, sum-rate 4 is achievable and there
are three optimal rate vectors for the non-asymptotic model.

C. Minimum Sum-rate
The condition for B(fα# , ≤) 6= ∅ can be easily derived based
on the intersecting submodularity of fα# .
Lemma III.2. For α ≥ 0, fα# is intersecting submodular; If
α ≥ H(V ), fα# is submodular.
Proof: For function fα# , we have
f # (X) + fα# (Y ) − fα# (X ∪ Y ) − fα# (X ∩ Y ) =
 α

H(X) + H(Y )
−H(X ∪ Y ) − H(X ∩ Y ) + α − H(V ) X ∩ Y = ∅ .


H(X) + H(Y ) − H(X ∪ Y ) − H(X ∩ Y ) otherwise
fα# (X)+ fα# (Y

fα# (X ∪Y

)+ fα# (X ∩Y

), ∀X, Y ⊆
)≥
Then,
V : X ∩ Y 6= ∅. Also, the inequality holds for all X, Y ⊆ V
when α ≥ H(V ). Lemma holds.
For X ⊆ V , denote by Π(X) the set that contains all
partitions of X. A partition P of X is the set that satisfies:
(a) C 6= ∅ for all C ∈ P; (b) C ∩ C ′ = ∅ for any distinctive
C, C ′ ∈ P; (c) ∪C∈P C = X. Denote Π′ (X) = Π(X)\{X} =
{P ∈ Π(X) : |P| > 1}. For a partition P ∈ Π(X), let
X
fα# [P] =
fα# (C)
C∈P

and
[32]

fˆα#

be the Dilworth truncation of fα# that is defined as
fˆα# (X) = min fα# [P],
P∈Π(X)

∀X ⊆ V.

(5)

We have fˆα# being a submodular function due to the intersecting submodularity of fα# [26, Theorems 2.5(i) and 2.6(i)]. It
is shown in [33, Section 3] that, for a given value of α, the
minimal/finest and maximal/coarsest partitions that minimize
minP∈Π(X) fα# [P] exist.14 We will show in the following
context that a condition on the Dilworth truncation determines
the nonemptiness of the base polyhedron B(fα# , ≤), based on
[33, Section 3], it is shown that the minimizers of minP∈Π(X) fα# [P]
form a partition lattice, which is called the Dilworth truncation lattice, where
the minimal/finest and maximal/coarsest minimizers uniquely exist.
14 In

which the value of the minimum sum-rate can be obtained
by a maximization problem over the partition set Π′ (V ).
In Section V-A, we will show that the minimum sum-rate
problem can be solved in polynomial time by the efficient
algorithms for solving the Dilworth truncation problem, the
minimization problem in (5).
Theorem III.3 ( [26, Theorems 2.5(i) and 2.6(i)]15). B(fα# , ≤
) is nonempty, i.e., α is achievable, and B(fα# , ≤) = B(fˆα# , ≤
) if and only if
α = fˆα# (V ).
(6)

0
1

7

In Theorem III.3, fˆα# (V ) = max{r(V ) : rV ∈ P (fα# , ≤)}
determines the maximum sum-rate of all rate vectors in
polyhedron P (fα# , ≤),16 while α is the sum-rate for all rate
vectors in the hyperplane {rV ∈ R|V | : r(V ) = α}. There
are two situations: if α > fˆα# (V ), P (fα# , ≤) does not
intersect with the hyperplane {rV ∈ R|V | : r(V ) = α};
if α = fˆα# (V ), P (fα# , ≤) intersects with the hyperplane
{rV ∈ R|V | : r(V ) = α} at B(fα# , ≤). In the latter case,
B(fα# , ≤) 6= ∅. Theorem III.3 can also be interpreted by the
principal sequence of partitions (PSP) in Appendix A.
Example III.4. For the system in Example II.1, it can be
shown that: when α < 72 , we have α > fˆα# (V ); when
α ≥ 27 , we have α = fˆα# (V ).17 For example, in Fig. 2 when
#
α = 16
5 , one can show that max{r(V ) : rV ∈ P (f16/5 , ≤)} =
#
#
fˆ16/5 (V ) = 13
5 < α. So, P (f16/5 , ≤) does not intersect with
#
hyperplane {rV ∈ R|V | : r(V ) = 16
5 }, i.e., B(fα , ≤) = ∅.
#
In Fig. 4, when α = 4, we have f4 being
f4# (∅) = 0, f4# ({1}) = 3, f4#({2}) = 1, f4# ({3}) = 1,
f4# ({1, 2}) = 4, f4#({1, 3}) = 4, f4#({2, 3}) = 3,
f4# ({1, 2, 3}) = 4
and the Dilworth truncation fˆ4# being
fˆ4# (∅) = 0, fˆ4# ({1}) = 3, fˆ4#({2}) = 1, fˆ4# ({3}) = 1,
fˆ# ({1, 2}) = 4, fˆ#({1, 3}) = 4, fˆ#({2, 3}) = 2,
4

4

4

fˆ4# ({1, 2, 3}) = 4.
One can show that max{r(V ) : rV ∈ P (f4# , ≤)} = fˆ4# (V ) =
4 = α and B(f4# , ≤) = B(fˆ4# , ≤) 6= ∅.
By comparing the values of f4# and fˆ4# , we can see
that the Dilworth truncation tightens the constraints in the
polyhedron P (f4# , ≤). For example, the inequality r({2, 3}) ≤
f4# ({2, 3}) = 3 in P (f4# , ≤) can be tightened by r({2}) ≤
f4# ({2}) = 1 and r({3}) ≤ f4# ({3}) = 1 so that we have
r({2, 3}) ≤ fˆ4# ({2, 3}) = 2 in P (fˆ4# , ≤). It also explains
that fˆα# (V ) determines the maximum sum-rate over all rate
vectors in the polyhedron P (fα# , ≤).
15 Theorem III.3 refers to the case when α < H(V ) in particular, since,
when α ≥ H(V ), fα# is submodular according to Lemma III.2 and α =
fα# (V ) = fˆα# (V ) and B(fα# , ≤) 6= ∅ for sure [26, Theorem 2.3].
16 fˆ# (V ) = r(V ), ∀r ∈ B(fˆ# , ≤) [26, Theorems 2.5(i) and 2.6(i)] and,
α
α
V
for each rV ∈ B(fˆα# , ≤), we have r(V ) = max{r(V ) : rV ∈ P (fˆα# , ≤

) = P (fα# , ≤)} [26, Theorems 2.3 and 2.5(i)]. A detailed explanation can
also be found in Appendix B.
17 The two situations can be seen from the fˆ# (V ) vs. α plot in Fig. 13.
α

8

IEEE TRANSACTIONS ON INFORMATION THEORY

Corollary III.5. For P ∈ Π′ (V ), define
ϕ(P) =

X H(V ) − H(C)
.
|P| − 1

C∈P

The minimum sum-rate in the asymptotic and non-asymptotic
models are respectively
RACO (V ) = max
ϕ(P),
P∈Π′ (V )


RNCO (V ) =
max
ϕ(P)
.
′
P∈Π (V )

(7a)
(7b)

Proof: Equation (6) in Theorem III.3 is equivalent to
α ≤ fα# [P], ∀P ∈ Π(V ), which can be converted to
α ≥ ϕ(P), ∀P ∈ Π′ (V ). It gives rise to the expressions of
RACO (V ) and RNCO (V ) in (7a) and (7b), respectively.
Remark III.6. It was first shown that RACO (V ) is lower
bounded by RACO (V ) ≥ maxP∈Π′ (V ) ϕ(P) in [4, Example 4] (see also Section III-E). In [19], [27], the authors
proved the tightness of this lower bound, where the same
result as (7a) in Corollary III.5 for the asymptotic model
is derived. However, the equality in (7a) in [19], [27] was
proved in a different way: Instead of showing the equivalence
B(fα# , ≤) = {rV ∈ RCO (V ) : r(V ) = α} and applying
[26, Theorems 2.5(i) and 2.6(i)] to prove the nonemptiness
of B(fα# , ≤), the authors defined a polyhedron P ′ (gα′ , ≤) =
{rV ∈ R|V | : r(X) ≤ gα′ (X), ∀X ⊆ V, X 6= ∅} for the
submodular function gα′ (X) = α − H(V ) + H(X), ∀X ⊆ V
and applied [34, Theorem 48.3] to show (7a). As compared
to the proof in [19, Section IV-B], our work in this section
shows that (7a) straightforwardly follows from [26, Theorems
2.5(i) and 2.6(i)],18 which also leads to our new derivation
of RNCO (V ) in (7b). In Section III-D, we show that (7b)
verifies an observation in [15, Section III-E] that the difference
between RACO (V ) and RNCO (V ) is bounded by one.
Corollary III.5 can be interpreted as follows. The minimum
sum-rate can be determined by a maximization over all multiway cuts of V . Any partition P ∈ Π′ (V ) can be considered
as a multi-way cut of the user set V . For any C ∈ P, the cut
{C, V \ C} imposes the SW constraint r(V \ C) ≥ H(V \
C|C)P
= H(V ) − H(C). By applying this toP
each C ∈ P, we
have  C∈P r(V \ C) = (|P| − 1)r(V ) ≥ C∈P H(V ) −
H(C) , which imposes requirement or lower bound
r(V ) ≥

X H(V ) − H(C)
= ϕ(P)
|P| − 1

C∈P

on the sum-rate for attaining omniscience. Here, |P| − 1 is a
normalization factor. Since the SW constraint applies to all the
subsets of V , an achievable sum-rate must satisfy the highest
requirement imposed by ϕ(P) over all multi-way cuts, i.e.,
ϕ(P) should be maximized over all P ∈ Π′ (V ). Therefore,
we have (7a) and (7b). We call the mininal/finest maximizer
of (7a) the fundamental partition and denote it by P ∗ .
′ , ≤) since we always have r(∅) = 0.
is clear that P (fα# , ≤) = P ′ (gα
In this sense, the proof in [19, Section IV-B] is essentially the same as the
proof of (7a) in this paper. However, the proof of Corollary (III.5) is much
simpler than [19, Section IV-B].
18 It

Example III.7. For the system in Example II.1, by applying
(7a) and (7b), we have RACO (V ) = 27 and RNCO (V ) = 4,
which are consistent with the results in Examples II.1 and
III.1. In addition, we have P ∗ = {{1}, {2}, {3}} being the
fundamental partition.
D. Related Results
Based on Corollary III.5, RNCO (V ) = ⌈RACO (V )⌉ so that
RNCO (V ) ≥ RACO (V ), i.e., the minimum sum-rate in the nonasymptotic model is no less than the one in the asymptotic
model, which is consistent with the results in [15], [16].
Based on (7a) and (7b) in Corollary III.5, it is straightforward that RACO (V ) + 1 > RNCO (V ). There is an observation
in [15, Section III-E] that the maximum difference between
RACO (V ) and RNCO (V ) is one transmission. Whereas the
result RNCO (V ) − RACO (V ) < 1 based on Corollary III.5
provides theoretical proof to this observation. It states that
the maximum difference between RACO (V ) and RNCO (V ) is
strictly less than one. Besides, we also have the following
results.
Theorem III.8. For all α ≥ RACO (V ), fˆα# is a polymatroid rank function and B(fˆα# , ≤) = B(fα# , ≤) = {rV ∈
RCO (V ) : r(V ) = α} 6= ∅.
Proof: According to the definition of function fα# and the
Dilworth truncation fˆα# , for all α ∈ R+ , we have fˆα# being
normalized, i.e., fˆα# (∅) = 0, and submodular [26, Theorem
2.5(i)]. The remaining task is to prove the monotonicity of
fˆα# when α ≥ RACO (V ). According to (7a), we have α ≥
RACO (V ) ≥ ϕ({{i}, V \{i}}) = 2H(V )−H({i}−H(V \{i})
for all i ∈ V . Then, when α ≥ RACO (V ),
fˆα# ({i}) = fα# ({i})
= α − H(V ) + H({i})
≥ H(V ) − H(V \ {i}) ≥ 0,
where the last inequality is due to the monotonicity of the
entropy function H. So, for all α ≥ RACO (V ) and i ∈ V ,
we have fˆα# ({i}) ≥ fˆα# (∅) and fˆα# (X) ≥ fˆα# (Y ) for all
X, Y ⊆ V such that i ∈ Y ⊆ X, i.e., fˆα# is monotonic.
According to Theorem III.3, when α ≥ RACO (V ), we have
α = fˆα# (V ) and B(fˆα# , ≤) = B(fα# , ≤) 6= ∅.
Theorem III.8 is important in proving the existence of
∗
a fractional and an integral rate vector in RACO
(V ) and
∗
RNCO (V ), respectively, in the finite linear source model and
CCDE.
Corollary III.9. In a finite linear source model,
∗
(a) there exists an integral optimal rate vector in RNCO
(V ).19
∗
(b) there exists a fractional optimal rate vector in RACO (V )
that can be implemented by (|P ∗ | − 1)-packet-splitting in
CCDE.
19 In fact, in a finite linear source model, there exists an integral rate
vector in B(fˆα# , ≤) = {rV ∈ RCO (V ) ∩ Z|V | : r(V ) = α} for all
α ∈ Z+ such that α ≥ RNCO (V ), which can be proved in the same way as
Corollary III.9(a). Corollary III.9(a) is consistent with the results derived in
[15], [18].

DING et al.: DETERMINING OPTIMAL RATES FOR COMMUNICATION FOR OMNISCIENCE

Proof: Recall that in a finite linear source model, the
entropy function H is integer-valued. Then, since fR#NCO (V ) is
integer-valued, based on Theorem III.8, fˆR#NCO (V ) is an integervalued polymatroid rank function. Denote by EX(fˆR#NCO (V ) )
the set of all extreme points, or vertices, in B(fˆR#NCO (V ) , ≤).
According to [26, Theorem 3.22], all rV ∈ EX(fˆR#NCO (V ) ) are
∗
integral and belong to B(fˆR#NCO (V ) , ≤) ∩ Z|V | = RNCO
(V ).
On the other
hand,
in
a
finite
linear
source
model,
we
have
P
RACO (V ) = C∈P ∗ H(V|P)−H(C)
according to Corollary III.5,
∗ |−1
i.e., RACO (V ) is a fractional number with denominator |P ∗ | −
1. So, RACO (V )(|P ∗ |−1) is integral. Then, (|P ∗ |−1)fR#ACO (V )
is an integer-valued polymatroid rank function. According to
[26, Theorem 3.22], all rV ∈ EX((|P ∗ | − 1)fˆR#ACO (V ) ) are
integral. For all rV ∈ EX((|P ∗ | − 1)fˆR#ACO (V ) ), |P ∗1|−1 rV ∈
∗
EX(fˆR#ACO (V ) ) ⊆ B(fˆR#ACO (V ) , ≤) = RACO
(V ) is a fractional
∗
optimal rate vector with |P | − 1 being the LCM of the
denominators of all dimensions. Corollary holds.
Example III.10. Consider the system in Example II.1. We
have RACO (V ) = 27 , RNCO (V ) = 4 and P ∗ = {{1}, {2}, {3}}.
From Fig. 4, it can be seen that the set of extreme points in
B(fˆR#NCO (V ) , ≤) is
n
o
EX(fˆR#NCO (V ) ) = (2, 1, 1), (3, 1, 0), (3, 0, 1) .

All rV ∈ EX(fˆR#NCO (V ) ) are the integral optimal rate vectors
∗
in RNCO
(V ). From Fig. 3, it can be seen that
n 5 1 1 o
EX(fˆR#ACO (V ) ) = ( , , ) = B(fˆR#ACO (V ) , ≤).
2 2 2
( 25 , 12 , 12 ) can be implemented by (|P ∗ | − 1)-packet-splitting.

Example III.11. Consider a different system compared to
previous examples where V = {1, . . . , 5} and each user
observes respectively
Z1 = (Wb , Wc , Wd , Wh , Wi ),
Z2 = (We , Wf , Wh , Wi ),
Z3 = (Wb , Wc , We , Wj ),
Z4 = (Wa , Wb , Wc , Wd , Wf , Wg , Wi , Wj ),
Z5 = (Wa , Wb , Wc , Wf , Wi , Wj ),
where Wj is an independent uniformly distributed random bit.
In this system, we have RACO (V ) = 13
2 , RNCO (V ) = 7 and
P ∗ = {{1, 4, 5}, {2}, {3}}. One can show that all rate vectors
∗
rV ∈ EX(fˆR#NCO (V ) ) ( B(fˆR#NCO (V ) , ≤) ∩ Z|V | = RNCO
(V )
∗
are integral, e.g., rV = (0, 1, 1, 5, 0). For RACO (V ) =
B(fˆR#ACO (V ) , ≤), the extreme point set is
n 1 1
5
1 1
5
EX(fˆR#ACO (V ) ) = (1, , , 2, ), (2, , , 1, ),
2 2
2
2 2
2
1 1 9
3 1 1
(1, , , , 0), ( , , , 4, 0),
2 2 2
2 2 2
o
3 1 1
( , , , 1, 3) .
2 2 2
We have |P ∗ | − 1 = 2 and all rate vectors in EX(fR#ACO (V ) )
can be implemented by 2-packet-splitting.

9

It is shown in [15, Section III-D] that (|V | − 1)-packetsplitting is sufficient to achieve the minimum sum-rate
RACO (V ) in a CCDE system with high probability.20 However,
Corollary III.9(b) states that (|P ∗ | − 1)-packet-splitting with
|P ∗ | − 1 ≤ |V | − 1 is sufficient to achieve the minimum sumrate RACO (V ) in a CCDE system for sure.
Remark III.12. The proof of Corollary III.9 states that
determining the integral and fractional optimal rate vectors in
∗
∗
(V ), respectively, is equivalent to search(V ) and RACO
RNCO
ing the extreme points in B(fˆR#NCO (V ) , ≤) and B(fˆR#ACO (V ) , ≤).
In Section V-C, we show the extreme points can be determined
by the MDA and SIA algorithms for the asymptotic and nonasymptotic models, respectively.
E. Secrecy Capacity and Mutual Dependence
The CO problem was first formulated in [4] based on the
study on secret capacity CS (A), the largest rate that the secret
key can be generated by the users in A. It is assumed that the
active users form a subset A ⊆ V and the others in V \ A are
the helpers that assist the active users generate the secret key.
The problem studied in this paper is the case when A = V ,
for which the following results are derived in [4]. The duality
relationship between CS (V ) and RACO (V ) has been revealed
in [4, Theorem 1]:

Let

RACO (V ) = H(V ) − CS (V ).

(8)

Q
D(PZV k C∈P PZC )
,
I(V ) = min
|P| − 1
P∈Π′ (V )

(9)

where D(·k·)
divergence and we have
P
Q is the Kullback-Leibler
D(PZV k C∈P PZC ) = C∈P H(C) − H(V ). It is shown in
[4, Example 4] that CS (V ) is upper bounded by
CS (V ) ≤ I(V )

(10)

Q

and D(PZV k C∈P PZC ) is interpreted as the mutual dependence for partition P ∈ Π′ (V ). Then, the minimum sum-rate
is necessarily lower bounded by RACO (V ) ≥ H(V ) − I(V ) =
maxP∈Π′ (V ) ϕ(P). There is also a conjecture in [4, Example
4] that the upper bound in (10) is tight.
By realizing that |P| − 1 is Qa normalization factor, the
D(PZV k C∈P PZC )
author in [27] proposed
to be the mutual
|P|−1
dependence measure for P ∈ Π′ (V ). The tightness of the
upper bound in (10) is shown in [27, Theorem 1]. In [19], I(V )
is proposed as the multivariate mutual information (MMI)
measure in ZV so that the duality relationship (8) is given
in terms of I(V ) in [7], [19], [20] as
RACO (V ) = H(V ) − I(V ),

(11)

Note, I(V ) is also called the shared information in [28]. The
interpretation of (11) is: the minimum sum-rate RACO (V ) must
be the amount of information that is not mutual to the users in
20 The authors in [15] study the more general CCDE system where each user
can only communicate with a subset of V . In the CCDE problem considered
in this paper, we assume that each user can communicate losslessly with all
other users, which is a special case of the general CCDE system in [15]. The
authors in [15] call the model studied in this paper a clique system.

10

IEEE TRANSACTIONS ON INFORMATION THEORY

4

mean error

mean error

6
4
2
0
15
10

|V |

5

10

15

20

25

30

2

0
15
10

|V |

H(V )

5

10

20

15

25

30

H(V )

Fig. 5. The average error incurred by (12), the lower bound on RNCO (V )
that is proposed in [8], in Experiment IV.3.

Fig. 6. The average error incurred by (13), the lower bound on RNCO (V )
that is proposed in [11], in Experiment IV.3.

V . The fundamental partition defined in [7], [19], [20] refers
to the finest/minimal minimizer of (9), the same as in this
paper. The dual relationship between RACO (V ) and CS (V ),
or I(V ), makes it more significant to study the minimum
sum-rate problem in CO: Determining the secret capacity
CS (V ) or MMI/shared information I(V ) relies on the efficient
algorithms for solving the minimum sum-rate problem and
vice versa.

In addition, if H({i}) = b for all i ∈ V , RNCO (V ) ≥ H(V ) −
b + 1, which can be explained by the LB
l X H(V ) − H({i}) m
RNCO (V ) ≥
|V | − 1
(13)
i∈V

IV. L OWER B OUND

ON

M INIMUM S UM -R ATE

The existing algorithms for solving the minimum sum-rate
problem in [15], [18] for the finite linear source model start
with an estimation of the minimum sum-rate. In this section,
we propose lower bounds (LBs) on RACO (V ) and RNCO (V )
that can be obtained in O(|V |) time. In Section V, we will
show that the LBs on RACO (V ) and RNCO (V ) can be used
as an initial guess to start the MDA and SIA algorithms for
searching the exact value of RACO (V ) and RNCO (V ) in the
asymptotic and non-asymptotic models, respectively.

= ⌈ϕ({{i} : i ∈ V })⌉

|
(H(V )−
proposed in [11] in that ⌈ϕ({{i} : i ∈ V })⌉ = ⌈ |V|V|−1
b)⌉ = H(V ) − b + 1 in the case when H({i}) = b, ∀i ∈ V .
But,

max ϕ({{i}, V \ {i}}) ≥ max H(V ) − H({i})
i∈V

i∈V

= H(V ) − min H({i}).
i∈V

The LB on RNCO (V ) in Proposition IV.1 is tighter than the
ones in [8], [11].

Experiment IV.3. We generate a number of CCDE systems
as follows. The number of packets H(V ) varies from 6 to 30,
while the number of users |V | varies from 3 to 15. For each
combination of H(V ) and |V |, we repeat the procedure below
Proposition IV.1. The minimum sum-rate is lower bounded for 20 times.
by
• randomly generate the packet sets zi = Ai x for all i ∈ V

subject to the condition l(x) = H(V );
RACO (V ) ≥ max ϕ({{i}, V \ {i}}), ϕ({{m} : m ∈ V }) ,
•
compute the LBs on RNCO (V ) based on [8], [11] and
i∈V 

Proposition
IV.1.
RNCO (V ) ≥ max ϕ({{i}, V \ {i}}), ϕ({{m} : m ∈ V }) .
i∈V
We obtain the error as the absolute difference between the LB
Proof: The LBs on RACO (V ) and RNCO (V ) are obtained and RNCO (V ). We plot the average error incurred by the LBs
by (7a) and (7b), respectively, by partitions P = {{i}, V \{i}} on RNCO (V ) in [8], [11] and Proposition IV.1 over repetitions
in Figs. 5, 6 and 7, respectively. It can be seen that the LB on
for all i ∈ V and partition P = {{m} : m ∈ V }.
The LBs in Proposition IV.1 can be obtained in O(|V |) time. RNCO (V ) in Proposition IV.1 is much tighter than the ones in
[8], [11]. In addition, the error in Fig. 7 is zero for |V | = 3
Remark IV.2. If |V | = 3, the LBs in Proposition IV.1 are tight according to Remark IV.2.
for both asymptotic and non-asymptotic models: If |V | = 3,
{{i}, V \ {i}} for all i ∈ V and {{m} : m ∈ V } constitute
all partitions in Π′ (V ). The tightness of the lower bound on V. A LGORITHMS FOR THE M INIMUM S UM - RATE P ROBLEM
RACO (V ) when |V | = 3 for the asymptotic model is consistent
The remaining problem is to discuss how to efficiently solve
with the result in [4, Example 3].
the maximization problems in (7a) and (7b) in Corollary III.5
The LB on RNCO (V ) has also been proposed in [8], [11] for the asymptotic and non-asymptotic settings, respectively,
for the finite linear source model. In [8], it is shown that
and determine a corresponding optimal rate vector. For this
purpose, we propose the MDA and SIA algorithms in this
RNCO (V ) ≥ H(V ) − min H({i}).
(12) section.
i∈V

DING et al.: DETERMINING OPTIMAL RATES FOR COMMUNICATION FOR OMNISCIENCE

6.6

·10−2

6.4
5

α

mean error

11

0
15

6.2

6
10

|V |

5

10

15

20

25

30

H(V )

estimation sequence of RACO (V )
RACO(V )

5.8
0

Fig. 7. The average error incurred by the lower bound on RNCO (V ) in
Proposition IV.1, in Experiment IV.3. The error is zero when |V | = 3
according to Remark IV.2.

Algorithm 1: Modified Decomposition Algorithm (MDA)
input : the ground set V , an oracle that returns the value of
H(X) for a given X ⊆ V
output: α that equals to RACO (V ), P ∗ which is the
fundamental partition and a rate vector rV in the
#
∗
optimal rate set RACO
(V ) = B(fˆR
, ≤)
ACO (V )
1

2

3
4
5
6

7
8
9

initialize α according
to Proposition IV.1:

α ← maxi∈V ϕ({{i}, V \ {i}}), ϕ({{m} : m ∈ V }) ;
find the minimal/finest minimizer P ∗ of minP∈Π(V ) fα# [P] and
a rate vector rV ∈ B(fˆα# , ≤);
α̂ ← ϕ(P ∗ );
while α̂ 6= α do
α ← α̂;
find the minimal/finest minimizer P ∗ of minP∈Π(V ) fα# [P]
and a rate vector rV ∈ B(fˆα# , ≤);
α̂ ← ϕ(P ∗ );
end
return α, P ∗ and rV ;

A. Modified Decomposition Algorithm
The MDA algorithm is given in Algorithm 1 for solving
the minimum sum-rate problem in the asymptotic model.
The optimality of the MDA algorithm is summarized in
Theorem V.1 below. The proof is in Appendix A-A.
Theorem V.1. The MDA algorithm outputs the minimum sumrate RACO (V ), the fundamental partition P ∗ and an optimal
∗
rate vector rV ∈ RACO
(V ) for the asymptotic model. The
estimation sequence of RACO (V ), i.e., the value of α in each
iteration, converges monotonically upward to RACO (V ).
Example V.2. We apply the MDA algorithm to
 the system
in Example III.11. We initiate α = maxi∈V ϕ({{i}, V \
{i}}), ϕ({{i} : i ∈ V }) = 23
4 as the LB on RACO (V ) in
Proposition IV.1, and have the following results.
23
∗
• When α = 4 , we have P = {{4, 5}, {1}, {2}, {3}}
being the minimal minimizer of the Dilworth
#
truncation
problem
minP∈Π(V ) f23/4
[P]
and
#
1
1 15
3
ˆ
rV = ( 4 , − 4 , − 4 , 4 , 0) being a vector in B(f23/4 , ≤).
We get α̂ = ϕ(P ∗ ) = 19
3 . Since α̂ 6= α, the iteration
continues;
19
∗
• When α = 3 , we have P = {{1, 4, 5}, {2}, {3}} being

1

2

3

iteration index
Fig. 8. The estimation sequence of RACO (V ), i.e., the value of α in each
iteration, when the MDA algorithm is applied to the system in Example III.11.
According to Theorem V.1, it converges monotonically upward to RACO (V ).
#
the minimal minimizer of minP∈Π(V ) f19/3
[P] and rV =
#
1 1 13
ˆ
(1, 3 , 3 , 3 , 0) ∈ B(f19/3 , ≤). Since α̂ = ϕ(P ∗ ) = 13
2 6=
α, the iteration continues;
13
∗
• When α = 2 , we have P = {{1, 4, 5}, {2}, {3}} being
#
the minimal minimizer of minP∈Π(V ) f13/2
[P] and rV =
#
1 1 9
ˆ
(1, 2 , 2 , 2 , 0) ∈ B(f13/2 , ≤). Since α̂ = ϕ(P ∗ ) = 13
2 =
α, the iteration terminates.
∗
At the output, α = 13
2 and P = {{1, 4, 5}, {2}, {3}} coincide
with the minimum sum-rate RACO (V ) and the fundamental
partition in Example III.11, respectively. In addition, rV =
#
∗
, ≤) = RACO
(V ) is an optimal rate
(1, 12 , 12 , 92 , 0) ∈ B(fˆ13/2
1 1 9
ˆ
vector. In fact, (1, 2 , 2 , 2 , 0) ∈ EX(fR#ACO (V ) ) is one of the
extreme points in the base polyhedron B(fR#ACO (V ) , ≤), where
EX(fR#ACO (V ) ) is shown in Example III.11. Fig. 8 shows that the
value of α in each iteration of the MDA algorithm converges
monotonically upwards to the minimum sum-rate RACO (V ).

In the next subsection, we show how to solve the Dilworth
truncation problem minP∈Π(V ) fα# [P] in steps 2 and 6 in the
MDA algorithm by a fusion implementation of the coordinatewise saturation capacity algorithm, where a rate vector rV ∈
B(fˆα# , ≤) is also returned.
B. Coordinate-wise Saturation Capacity Algorithm by Fusion
Method
There exist several algorithms for solving the Dilworth
truncation problem minP∈Π(V ) fα# [P] in the literature. For
example, the fusion set method is proposed in [31], [33] for
determining the PSP of electronic networks; The coordinatewise saturation capacity (CoordSatCap) algorithm in [26,
Section 3.2] has been applied to determine the PSP of a
network in [35, Algorithm A], [36, Section 2] and the strength
of a network in [37, Section 3].21
In this paper, we consider the CoordSatCap algorithm,
which determines not only the minimum and the minimizer of
21 One can verify that the methods in [35, Algorithm A], [36, Section 2]
and [37, Section 3] are in fact the CoordSatCap algorithm that is presented as
Greedy Algorithm II in [26, Section 3.2]. The studies in [35]–[37] are based
on the cut function of a network.

12

IEEE TRANSACTIONS ON INFORMATION THEORY

the Dilworth truncation problem minP∈Π(V ) fα# [P], but also
a rate vector rV in the base polyhedron B(fˆα# , ≤). In this
section, we first describe the CoordSatCap algorithm and then
show how to implement it by a fusion method.
We introduce some related definitions as follows. For X ⊆
V , let χX = (ri : i ∈ V ) be the characteristic vector of the
subset X such that ri = 1 if i ∈ X and ri = 0 if i ∈
/ X.
The notation χ{i} is simplified by χi . Let Φ = (φ1 , . . . , φ|V | ),
where φi ∈ V and φi 6= φi′ for all i, i′ ∈ {1, . . . , |V |} such
that i 6= i′ . We call Φ a linear ordering of V . For example,
Φ = (2, 3, 1, 4) is a linear ordering of V = {1, . . . , 4}.
For U ⊆ P where P is some partition in Π(V ), denote

Algorithm 2: Coordinate-wise Saturation Capacity (CoordSatCap) Algorithm [26]
input : the ground set V , an oracle that returns the value of
H(X) for a given X ⊆ V , α which is an estimation
of RACO (V )
output: rV which is a rate vector in B(fˆα# , ≤) and P ∗ which
is the minimal/finest minimizer of minP∈Π(V ) fα# [P]
1
2
3

initiate rV so that rV ∈ P (fα# , ≤) and P ∗ = {{i} : i ∈ V }
and choose a linear ordering Φ = (φ1 , . . . , φ|V | );
for i = 1 to |V | do
determine the saturation capacity
ξ̂φi ← min{fα# (X) − r(X) : φi ∈ X ⊆ V }
and the minimal/smallest minimizer X̂φi ;
rV ← rV + ξˆφi χφi ;
merge/fuse all subsets in P ∗ that intersect with X̂φi in to
one subset X̃ = ⊔X∈X X:

Ũ = ⊔X∈U X
4

where ⊔ is the disjoint union, i.e., Ũ ⊆ V is a fusion of all the subsets in U . For example, for P =
{{1, 3}, {2, 4}, {5}, {6}, {7}} ∈ Π({1, . . . , 7}) and U =
{{1, 3}, {2, 4}, {5}, {6}} ( P, we have Ũ = {1, . . . , 6}.
For a rate vector rV ∈ P (fα# , ≤),
ξ̂i = max{ξ : rV + ξχi ∈ P (fα# , ≤)}
is called the saturation capacity in dimension i [26, Section
2.3]. Here, ξˆi ∈ R+ denotes the maximum increment in
ri such that the resulting rate vector rV + ξ̂i χi is still in
the polyhedron P (fα# , ≤). The saturation capacity can be
determined by solving the minimization problem [26, Section
2.3]
max{ξ : rV + ξχi ∈ P (fα# , ≤)} =
min{fα#(X)

− r(X) : i ∈ X ⊆ V }. (14)

Here, fα# is submodular over all X ⊆ V such that i ∈ X
because of the intersecting submodularity of fα# , i.e., the
minimization problem in (14) is an SFM one. An SFM
problem can be solved in polynomial time [38]–[43] (see
also Section V-D). The minimizers of an SFM problem form
a lattice, where the minimal/smallest and maximal/largest
minimizer exist [26, Lemma 2.1]. In Step 3 of Algorithm 2,
we obtain the minimal/smallest minimizer.
1) Coordinate-wise Saturation Capacity (CoordSatCap) Algorithm: The main purpose of the CoordSatCap algorithm in
Algorithm 2 is to determine a rate vector, or base point, in
B(fˆα# , ≤). The idea is to start with a point rV ∈ P (fα# , ≤)
and increase each dimension of rV in order by the saturation
capacity. Finally, we have rV still in P (fα# , ≤) but reaching
saturation in each dimension, i.e., rV + ǫχi ∈
/ P (fα# , ≤)
for all ǫ > 0 and i ∈ V , which means rV ∈ B(fˆα# , ≤)
necessarily. Based on the tight sets of this base point, the
minimizers of minP∈Π(V ) fα# [P] can be determined, i.e., the
Dilworth truncation problem is solved accordingly.22 See also
Appendix B for the detailed explanation of the CoordSatCap
algorithm.
22 The definition of tight set and related explanations are in Appendix B,
where we also present a brief proof/explanation that the CoordSatCap algorithm outputs a rate vector rV ∈ B(fˆα# , ≤) and the minimal minimizer P ∗
of the Dilworth truncation problem minP∈Π(V ) fα# [P] based on the studies
in [25], [26], [37].

5

X ← {C ∈ P ∗ : C ∩ X̂φi 6= ∅};
P ∗ ← (P ∗ \ X ) ⊔ {X˜ };
6
7

endfor
return rV and P ∗ ;

The following lemma shows one way to initiate a rate vector
rV such that rV ∈ P (fα# , ≤). The proof is in Appendix B-B.
Lemma V.3. For any α such that 0 ≤ α ≤ H(V ), rV =
(α − H(V ))χV ∈ P (fα# , ≤).
In Algorithm 2, the linear ordering Φ matters when we
want to minimize a weighted sum-rate objective function in
the optimal rate set, which will be discussed in Section VI.
We remark that for the minimum (equal-weight) sum-rate
problem for both asymptotic and non-asymptotic models that
is considered in this section, any linear ordering Φ of the user
indices can be chosen.
Example V.4. Consider the Dilworth truncation problem
minP∈Π(V ) fα# [P] for α = 23
4 in Example V.2. We apply the CoordSatCap algorithm by initiating rV = (α −
17
H(V ))χV = (− 17
4 , . . . , − 4 ) according to Lemma V.3 and
∗
P = {{1}, {2}, {3}, {4}, {5}}. The linear ordering is set to
Φ = (4, 5, 3, 2, 1).
•

•

•

For φ1 = 4, we have ξ̂4 = 8 and X̂4 = {4} being
#
the minimum and minimal minimizer of min{f23/4
(X) −
r(X) : 4 ∈ X ⊆ V }, respectively. By executing rV ←
17
17 15
17
rV + 8χ4 , we update rV to (− 17
4 , − 4 , − 4 , 4 , − 4 ).
∗
Also, X = {{4}} and X̃ = {C ∈ P : C ∩ {4} =
6 ∅} =
{4}. By executing P ∗ = (P ∗ \ X ) ⊔ {X̃ }, we still have
P ∗ = {{1}, {2}, {3}, {4}, {5}};
For φ2 = 5, we have ξ̂5 = 17
4 and X̂5 = {4, 5}. rV
17
17 15
,
−
,
−
,
is updated to (− 17
4
4
4
4 , 0). Since X = {C ∈
P ∗ : C ∩ {4, 5} =
6 ∅} = {{4}, {5}} and X˜ = {4, 5},
by executing P ∗ = (P ∗ \ X ) ⊔ {X̃ }, we update P ∗ to
{{1}, {2}, {3}, {4, 5}};
For φ3 = 2, we have ξˆ2 = 4 and X̂2 =
1
17 15
∗
=
{2}. rV is updated to (− 17
4 , − 4 , − 4 , 4 , 0). P
∗
∗
{{1}, {2}, {3}, {4, 5}} after executing P = (P \ X ) ⊔

DING et al.: DETERMINING OPTIMAL RATES FOR COMMUNICATION FOR OMNISCIENCE

13

#
B(fˆ13/2,C
, ≤)
#
P (f13/2,C , ≤)

#
, ≤)
B(fˆ23/4,C
#
P (f23/4,C , ≤)

path to ( 34 , 15
4 , 0)

0
−1

r5

r5

1

−2
−3
−4
5

path to (1, 29 , 0)

#
EX(fˆ23/4,C
)

2

4

5
3

2

r4

1

0
−1
−2
−3
−4 −4

−3

−2

−1

0

1

2

EX(fˆR#ACO (V ),C )

3
2
1
0
−1
−2
−3
4

3

2

r4

r1

and C = {1, 4, 5}, the figure shows the polyhedron
Fig. 9. For α = 23
4
#
#
#
is the reduc, ≤), where fα,C
, ≤) and base polyhedron B(fˆα,C
P (fα,C
#
tion of fα on C. Note, in this case, the base polyhedron B(fˆ# , ≤)
α,C

reduces to a line segment with two vertices, ( 34 , 15
, 0) and ( 34 , 2, 74 ). This
4
figure also shows the adaptation of the rate vector rC resulted from the
, − 17
, − 17
)→
CoordSatCapFus algorithm in Example V.4: the path (− 17
4
4
4
15
17
17 15
3 15
(− 17
,
,
−
)
→
(−
,
,
0)
→
(
,
,
0).
We
have
the
rate
vector
4
4
4
4
4
4 4
#
( 34 , 15
, ≤) at the end.
, 0) ∈ B(fˆα,C
4

{X̃ };
For φ4 = 3, we have ξ̂3 = 4 and X̂3 =
1
1 15
∗
=
{3}. rV is updated to (− 17
4 , − 4 , − 4 , 4 , 0). P
∗
∗
{{1}, {2}, {3}, {4, 5}} after executing P = (P \ X ) ⊔
{X̃ };
• For φ5
= 1, we have ξ̂1 = 5 and X̂1 =
∗
=
{1}. rV is updated to ( 34 , − 41 , − 14 , 15
4 , 0). P
∗
∗
{{1}, {2}, {3}, {4, 5}} after executing P = (P \ X ) ⊔
{X̃ }.
At the output, we have P ∗ = {{1}, {2}, {3}, {4, 5}} and
rV = ( 34 , − 41 , − 14 , 15
4 , 0) being the minimal minimizer of
#
#
minP∈Π(V ) f23/4
[P] and a base point in B(fˆ23/4
, ≤), respectively.
•

Example V.5. Consider the Dilworth truncation problem
minP∈Π(V ) fα# [P] for α = 13
2 in Example V.2. By applying the
CoordSatCap algorithm in the same way as in Example V.4,
one can show that, at the output, P ∗ = {{1, 4, 5}, {2}, {3}}
and rV = (1, 21 , 21 , 92 , 0), which are the minimal minimizer
#
#
of minP∈Π(V ) f13/2
[P] and a rate vector in B(fˆ13/2
, ≤),
respectively.
#
#
For C ⊆ V , we call fα,C
: 2C 7→ R with fα,C
(X) =
fα# (X) for all X ⊆ C the reduction of fα# on C [26, Section
#
3.1(a)]. The polyhedron and base polyhedron of fα,C
are
respectively
#
#
P (fα,C
, ≤) = {rC ∈ R|C| : r(X) ≤ fα,C
(X), X ⊆ C},
#
#
#
B(fα,C
, ≤) = {rC ∈ P (fα,C
, ≤) : r(C) = fα,C
(C)}.
#
#
In Fig. 9, we show P (fα,C
, ≤) and B(fˆα,C
, ≤) when α = 23
4
and C = {1, 4, 5}, where we can see the the path to
rC = ( 34 , 15
4 , 0) as a result of the CoordSatCap algorithm in
#
#
Example V.4. In Fig. 10, we show P (fα,C
, ≤) and B(fˆα,C
, ≤)

1

0

−1
−2
−3

−3

−2

−1

0

1

2

3

r1

Fig. 10.
For α = 13
and C = {1, 4, 5}, the figure shows
2
#
#
, ≤). In this
, ≤) and base polyhedron B(fˆα,C
the polyhedron P (fα,C
case, the base polyhedron is a 2-dimensional polygon with five ver#
tices that constitutes the extreme points set EX(fˆR
) =
ACO (V ),C
5
5
9
3
3
{(1, 2, 2 ), (2, 1, 2 ), (1, 2 , 0), ( 2 , 4, 0), ( 2 , 1, 3)}. This figure also shows
the adaptation of the rate vector rC resulted from the CoordSatCapFus
algorithm in Example V.5: the path (− 72 , − 27 , − 72 ) → (− 72 , 92 , − 27 ) →
#
(− 72 , 29 , 0) → (1, 92 , 0). We have the rate vector (1, 29 , 0) ∈ B(fˆα,C
, ≤) at
the end.

when α = 13
2 and C = {1, 4, 5}, where we can see the the path
to rC = (1, 29 , 0) as a result of the CoordSatCap algorithm in
Example V.5.
2) A Fusion Method Implementation: In the CoordSatCap
algorithm, the saturation capacity ξφi in dimension φi is
determined by solving problem min{fα# (X) − r(X) : φi ∈
X ⊆ V }, where each element in V is the index of a user
in the system. In this section, we show that this problem can
be solved over a merged user set where each non-singleton
element denotes a super user, i.e., the CoordSatCap algorithm
can be implemented by a fusion method. The validity of
this fusion method is based on Lemma V.6 and Lemma V.7
below with the proofs in Appendix B-C and Appendix B-D,
respectively.
Lemma V.6. Let the CoordSatCap algorithm start with a
rate vector rV ∈ P (fα# , ≤) such that rV ≤ 0, where
0 = (0, . . . , 0) ∈ R|V | . We have
min{fα# (X) − r(X) : φi ∈ X ⊆ V } =
min{fα#(X) − r(X) : φi ∈ X ⊆ Vi }, (15)
where Vi = {φ1 , . . . , φi } and the minimal minimizer X̂φi ⊆ Vi
for all i ∈ {1, . . . , |V |}.
The equality (15) in Lemma V.6 was originally derived in
the proof of [26, Theorem 3.19], based on which the authors
in [15], [18] apply min{fα#(X) − r(X) : φi ∈ X ⊆ Vi }
in the CoordSatCap algorithm for solving the non-asymptotic
minimum sum-rate problem in the finite linear source model
and CCDE. However, the proof of [26, Theorem 3.19] does
not show that X̂φi ⊆ Vi for all i.

14

IEEE TRANSACTIONS ON INFORMATION THEORY

Lemma V.7. In the CoordSatCap algorithm,
min{fα# (X) − r(X) : φi ∈ X ⊆ V } =
min{fα# (Ũ )

∗

− r(Ũ ) : U ⊆ P , φi ∈ Ũ }

Algorithm 3: Coordinate-wise Saturation Capacity Algorithm by Fusion Method (CoordSatCapFus)

(16)

input : the ground set V , an oracle that returns the value of
H(X) for a given X ⊆ V , α which is an estimation
of RACO (V )
∗
output: rV which is a rate vector in B(fˆα# , ≤) and P|V
| which
is the minimal/finest minimizer of minP∈Π(V ) fα# [P]

(17)

for all i ∈ {1, . . . , |V |}. Let X̂φi and Uφ∗i be the minimal
minimizer of the (16) and (17), respectively. X̃ = Ũφ∗i , where
X = {C ∈ P ∗ : C ∩ X̂φi 6= ∅}.
Both minimization problems, (16) and (17), in Lemma V.7
are SFM problems due to the intersecting submodularity of
fα# . But, P ∗ is a fused user set since some of the users have
been merged into a super user set, which is treated as one
dimension in the SFM problem (17). So, |P ∗ | ≤ |V |. We will
show in Section V-D that minimizing over the fused user set
contributes to a reduction in computation complexity.
Remark V.8. Lemma V.7 is based on the fact: If X̂φi is a nonsingleton minimal minimizer of min{fα# (X) − r(X) : φi ∈
X ⊆ V } for some φi , then, for any partition P that
crosses X̂φi , there exists a P ′ that does not cross X̂φi such
that fα# [P ′ ] < fα# [P].23 It means that, to determine the
minimal/finest minimizer of the Dilworth truncation problem
minP∈Π′ (V ) fα# [P], we just need to consider all the partitions
in Π(V ) that do not cross X̂φi .24 See Appendix B-E for the
explanation.
Example V.9. In Exmaple V.4, we have X̂5 = {4, 5} when
α = 23
4 . For P = {{1, 4}, {2, 3}, {5}} that crosses {4, 5}, we
have P ′ = {{1, 4, 5}, {2, 3}} that does not cross {4, 5} such
37
#
that fα# [P ′ ] = 15
2 < fα [P] = 4 ; For P = {{1, 4}, {2, 3, 5}}
that crosses {4, 5}, we have P ′ = {{4, 5}, {1}, {2, 3}} that
17
#
does not cross {4, 5} such that fα# [P ′ ] = 29
4 < fα [P] = 2 .
One can show that for each partition P that crosses {4, 5}
there always exists a partition P ′ that does not cross {4, 5}
such that fα# [P ′ ] < fα# [P]. Therefore, we just need to
consider all partitions that do not cross {4, 5} to determine
the minimal minimizer of minP∈Π′ (V ) fα# [P]. It is equivalent
to considering all partitions of {{4, 5}, {1}, {2}, {3}}, which
is the value of P ∗ when φ2 = 5 in Exmaple V.4.
Based on Lemmas V.6 and V.7, the CoordSatCap algorithm
in Algorithm 2 is equivalent to the CoordSatCapFus algorithm
in Algorithm 3. Steps 4, 5 and 7 in Algorithm 3 are explained
as follows.
According to Lemmas V.6 and V.7, the saturation capacity
can be obtained by ξ̂φi = min{fα#(Ũ ) − r(Ũ ) : {φi } ∈
∗
U ⊆ Pi∗ }. Here, Pi∗ = Pi−1
⊔ {{φi }} ∈ Π(Vi ) with
∗
Pi−1 ∈ Π(Vi−1 ) being the partition obtained at the end
of iteration i − 1. For the minimal minimizer Uφ∗i of this
problem, we have X̂φi ⊆ X˜ = Ũφ∗i , where X̂φi is the
minimal minimizer of min{fα# (X) − r(X) : φi ∈ X ⊆ Vi }
and X = {C ∈ Pi∗ : C ∩ X̂φi 6= ∅}. This explains steps 4 and 5
23 A multi-way cut or partition P ∈ Π′ (V ) does not cross a set X ( V
if there exist C ∈ P such that X ⊆ C. For example, for X = {1, 3},
{{1, 3, 4}, {2}} and {{1, 3}, {2}, {4}} are the partitions that do not cross
X, while {{1, 2}, {3}, {4}} and {{1}, {2, 3, 4}} are the partitions that cross
X.
24 In addition, the fundamental partition P ∗ must be a multi-way cut of V
that does not cross X̂φi . See Appendix B-E.

1
2
3
4
5

let rV ← (α − H(V ))χV so that rV ∈ P (fα# , ≤) and choose
a linear ordering Φ = (φ1 , . . . , φ|V | );
initiate rφ1 ← fα# ({φ1 }) and P1∗ ← {{φ1 }};
for i = 2 to |V | do
∗
Pi∗ ← Pi−1
⊔ {{φi }};
determine the saturation capacity
ξ̂φi ← min{fα# (Ũ ) − r(Ũ ) : {φi } ∈ U ⊆ Pi∗ }
and the minimal/smallest minimizer Uφ∗i ;
rV ← rV + ξˆφi χφi ;
merge/fuse all subsets in Uφ∗i into one subset
Ũφ∗i = ⊔X∈Uφ∗ X:

6
7

i

Pi∗ ← (Pi∗ \ Uφ∗i ) ⊔ {Ũφ∗i };
8
9

endfor
∗
return rV and P|V
|;

in Algorithm 3. The equality X̃ = Ũφ∗i also makes the update
of Pi∗ easier: We do not need to obtain X as we did in step 5
in Algorithm 2. Since (Pi∗ \ Uφ∗i ) ⊔ {Ũφ∗i } = (Pi∗ \ X ) ⊔ {X˜ },
simply do Pi∗ ← (Pi∗ \ Uφ∗i ) ⊔ {Ũφ∗i }, which does not require
the determination of X . This explains step 7 in Algorithm 3.
Since the saturation capacity in the CoordSatCapFus algorithm is always obtained by a minimization problem over a
fused user set P ∗ ∈ Π(Vi ) for all i ∈ {1, . . . , |V |}, we call the
CoordSatCapFus algorithm a fusion method implementation of
the CoordSatCap algorithm.
Example V.10. Consider the Dilworth truncation problem
minP∈Π(V ) fα# [P] when α = 23
4 in Example V.2. We apply
the CoordSatCapFus algorithm by initiating rV = (α −
17
H(V ))χV = (− 17
4 , . . . , − 4 ). The linear ordering is set to
Φ = (4, 5, 3, 2, 1).
•

•

#
For φ1 = 4, we assign r4 = f23/4
({4}) = 15
4 so that
17
17 15
17
17
∗
rV = (− 4 , − 4 , − 4 , 4 , − 4 ) and let P1 = {{4}};
For φ2 = 5, we have P2∗ = {{4}, {5}} and consider the
problem min{fα#(Ũ ) − r(Ũ ) : {5} ∈ U ⊆ P2∗ }. Since
{U : {5} ∈ U ⊆ P2∗ } = {{{5}}, {{4}, {5}}} and
#
f23/4
({5}) − r({5}) = 6,
#
f23/4
({4, 5}) − r({4, 5}) =

•

17
,
4

∗
we have ξ̂5 = 17
4 and U5 = {{4}, {5}}. rV and
17
17
15
∗
P2 are updated to (− 4 , − 4 , − 17
4 , 4 , 0) and {{4, 5}},
respectively;
For φ3 = 2, we have P3∗ = {{2}, {4, 5}} and consider
the problem min{fα#(Ũ ) − r(Ũ ) : {2} ∈ U ⊆ P3∗ }. Since

DING et al.: DETERMINING OPTIMAL RATES FOR COMMUNICATION FOR OMNISCIENCE

{U : {2} ∈ U ⊆ P3∗ } = {{{2}}, {{2}, {4, 5}}} and
#
f23/4
({2}) −

25
,
4

we have ξ̂2 = 4 and U2∗ = {{2}}. rV and P3∗ are updated
1
17 15
to (− 17
4 , − 4 , − 4 , 4 , 0) and {{2}, {4, 5}}, respectively;
• In the same way, we can show the followings at the end
of each iteration.
15
∗
– For φ4 = 3, rV = (− 14 , − 14 , − 17
4 , 4 , 0) and P4 =
{{2}, {3}, {4, 5}};
15
∗
– For φ5 = 1, rV = ( 34 , − 14 , − 17
4 , 4 , 0) and P5 =
{{1}, {2}, {3}, {4, 5}}.
15
∗
At the end, we have r = ( 34 , − 41 , − 17
4 , 4 , 0) and P5 =
{{1}, {2}, {3}, {4, 5}}, which are the same as in Example V.4.
It can be seen that the CoordSatCapFus outputs the same
results as in Example V.5 for the Dilworth truncation problem
#
minP∈Π(V ) f13/2
[P].
C. Solutions for the Finite Linear Source Model
As discussed in Section II-B, in a finite linear source
model, we are particularly interested in the existence of the
∗
fractional and integral optimal rate vectors in RACO
(V ) and
∗
RNCO (V ), respectively. As pointed out in Remark III.12,
∗
since the extreme points in RACO
(V ) = B(fˆR#ACO (V ) , ≤)
∗
and RNCO
(V ) = B(fˆR#NCO (V ) , ≤) ∩ Z|V | are fractional and
integral, respectively, in a finite linear source model, the
problem reduces to determining a rate vector in EX(fˆR#ACO (V ) )
and EX(fˆR#NCO (V ) ). For this purpose, we have the following
theorem with the proof in Appendix C.
Theorem V.11. For all α ≥ RACO (V ), the CoordSatCap
algorithm returns rV that is an extreme point, or a vertex,
in B(fˆα# , ≤), i.e., rV ∈ EX(fˆα# ).
According to Theorem V.11 and the proof of Corollary III.9,
we have the following results straightforwardly.
Corollary V.12. For a finite linear source model,
∗
(a) the MDA algorithm outputs rV ∈ RACO
(V ) such that
∗
(|P | − 1)rV is integral, i.e., rV can be implemented by
(|P ∗ | − 1)-packet-splitting in CCDE;
(b) with input α = RNCO (V ), the CoordSatCapFus algorithm
∗
returns rV ∈ RNCO
(V ) which is integral.
If the value of RACO (V ) can be determined by the MDA
algorithm, we know automatically RNCO (V ) = ⌈RACO (V )⌉.
Then, according to Corollary V.12, we can determine an in∗
tegral optimal rate vector in RNCO
(V ) for the non-asymptotic
model in a finite linear source model by no more than one
additional call of the CoordSatCapFus algorithm.25
25 If

Algorithm 4: sum-rate increment algorithm (SIA) for
solving the non-asymptotic minimum sum-rate problem in
the finite linear source model

r({2}) = 4,

#
f23/4
({2, 4, 5}) − r({2, 4, 5}) =

RACO (V ) = RNCO (V ), RACO (V ) is integral necessarily and the
∗ (V ) returned by the MDA algorithm is also an inrate vector in RACO
∗ (V ); If R
tegral rate vector in RNCO
ACO (V ) < RNCO (V ), an integral
∗ (V ) can be determined by an extra call
optimal rate vector in RNCO
CoordSatCapFus(V, H, ⌈RACO (V )⌉). Therefore, in a finite linear source
model, the non-asymptotic minimum sum-rate problem can be solved by no
more than one extra call of the CoordSatCapFus algorithm after obtaining
RACO (V ).

15

input : the ground set V , an oracle that returns the value of
H(X) for a given X ⊆ V
output: a rate vector rV in the optimal rate set
#
∗
RNCO
(V ) = B(fˆR
, ≤) ∩ Z|V | and α which
NCO (V )
equals to RNCO (V )
1

2
3
4
5
6
7

initialize
 to Proposition IV.1:

 α according
α ← maxi∈V ϕ({{i}, V \ {i}}), ϕ({{m} : m ∈ V }) ;
determine a rate vector rV ∈ B(fˆα# , ≤) by solving the problem
minP∈Π(V ) fα# [P];
while r(V ) 6= α do
α ← α + 1;
determine a rate vector rV ∈ B(fˆα# , ≤) by solving the
problem minP∈Π(V ) fα# [P];
end
return rV and α;

Example V.13. The optimal rate vector rV = (1, 12 , 12 , 92 , 0) ∈
∗
RACO
(V ) determined by the MDA algorithm in Example V.2
∗
is an extreme point in B(fˆR#ACO (V ) , ≤) = RACO
(V ), i.e.,
#
#
1 1 9
ˆ
ˆ
rV = (1, 2 , 2 , 2 , 0) ∈ EX(fRACO (V ) ), where EX(fRACO (V ) ) is
shown in Example III.11. Recall that the fundamental partition
in this system is P ∗ = {{1, 4, 5}, {2}, {3}} so that |P ∗ | = 3.
Therefore, rV = (1, 12 , 21 , 92 , 0) can be implemented by 2packet-splitting.
Since RACO (V ) = 13
2 , we have RNCO (V ) = ⌈RACO (V )⌉ =
7. By setting the linear ordering Φ = (4, 5, 2, 3, 1), we call
CoordSatCapFus(V, H, 7) and have rV = (0, 1, 1, 5, 0) and
P ∗ = {{1, 2, 3, 4, 5}} at the output. One can show that rV =
∗
(0, 1, 1, 5, 0) ∈ EX(fˆ7# ) ( B(fˆ7# , ≤) ∩ Z|5| = RNCO
(V ).26
On the other hand, we can also adopt a proper sum-rate
adaptation method to solve the non-asymptotic minimum sumrate problem in the finite linear source model. This idea was
originally proposed in [15], [18]. The method is to iteratively
update α, the estimation of the minimum sum-rate RNCO (V ),
on an integer set in Z+ until it reaches RNCO (V ). The
implementation of this method requires: (a) a method that
can check if a sum-rate α is achievable; (b) an algorithm
that can determine a rate vector rV ∈ B(fˆα# , ≤) = {rV ∈
RCO (V ) : r(V ) = α} if α is achievable. It is fortunate that the
CoordSatCap and CoordSatCapFus algorithms can complete
both tasks.
Corollary V.14. For a sum-rate α, let rV be the rate vector
returned by the CoordSatCapFus, or CoordSatCap, algorithm:
α is achievable if and only if r(V ) = α; If α is achievable, we
have rV ∈ B(fˆα# , ≤) = {rV ∈ RCO (V ) : r(V ) = α} being
an achievable rate vector with sum-rate α.
The proof of Corollary V.14 is in Appendix C. According
to Corollary V.14, we can start with a lower estimation α of
RNCO (V ), e.g., the LB in Proposition IV.1, and increase α by
26 The result P ∗ = {{1, 2, 3, 4, 5}} is consistent with property (a) of the
PSP in Theorem A.2 in Appendix A: Since RNCO (V ) > RACO (V ) =
α1 , {V } is the only minimizer of the Dilworth truncation problem
#
minP∈Π(V ) fR
[P].
(V )
NCO

16

one until it is achievable. The first achievable α necessarily
equals to RNCO (V ). Since RNCO (V ) ∈ {0, 1, . . . , H(V )}, we
can adjust α to RNCO (V ) within a finite number of iterations.
This idea is implemented by the SIA algorithm in Algorithm 4,
where the Dilworth truncation problem minP∈Π(V ) fα# [P]
in steps 2 and 5 can be solved by the CoordSatCap or
CoordSatCapFus algorithm.
Example V.15. We apply the SIA algorithm
to
 the system

ϕ({{i}, V \
in Example III.11. We initiate
α
=
max
i∈V

{i}}), ϕ({{m} : m ∈ V })
= 6 according to Proposition IV.1. We implement the CoordSatCapFus algorithm for
solving the Dilworth truncation problem minP∈Π(V ) fα# [P].
∗
• For α = 6, we have rV = (1, 0, 0, 4, 0) and P
=
{{4, 5}, {1}, {2}, {3}} returned by the CoordSatCapFus
algorithm. Since r(V ) = 5 < α, we update α to 7 and
continue the iteration;
∗
• For α = 7, we have rV = (0, 1, 1, 5, 0) and P
=
{{1, 2, 3, 4, 5}} returned by the CoordSatCapFus algorithm. Since r(V ) = 7 = α, the iteration terminates.
∗
At the output, we have rV = (0, 1, 1, 5, 0) ∈ RNCO
(V ),
which is consistent with the result in Example V.13. Here, the
SIA algorithm solves the non-asymptotic minimum sum-rate
problem in the finite linear source model without obtaining
the value of RACO (V ).
Note, in the SIA algorithm, the updates of α do not
require the minimal/finest minimizer of the Dilworth truncation problem minP∈Π(V ) fα# [P].27 On the other hand, the
sum-rate adaptation method is not unique. For solving the
non-asymptotic minimum sum-rate problem in CCDE, the
authors in [15], [18] proposed efficient algorithms to update
α to RNCO (V ), where the CoordSatCap algorithm based
on Lemma V.6 is implemented as a subroutine. Since the
CoordSatCap and CoordSatCapFus algorithms accomplish the
same tasks in Corollary V.14, we can replace the CoordSatCap
algorithm by the CoordSatCapFus algorithm in the sum-rate
adaptation algorithms in [15], [18]. In the next subsection, we
will show the advantage of this replacement: the reduction in
complexity.
D. Complexity
Let δ be the computation complexity of evaluating the
value of a submodular function f : 2V 7→ R.28 We denote O(SFM(|V |)) the complexity of solving the submodular
function minimization (SFM) problem min{f (X) : X ⊆ V },
which is strongly polynomial [38]–[43]. For example, the SFM
algorithm proposed in [44] completes in O(|V |5 ·δ+|V |6 ) time,
which is the most efficient SFM algorithm in the literature
to the best of our knowledge. Also, the minimizers of an
SFM problem form a lattice, where the minimal/smallest and
27 It means that, when applied to the SIA algorithm, the initiation and
updates of P ∗ in the CoordSatCap algorithm and Pi∗ in the CoordSatCapFus
algorithm are not required. In addition, the determination of the minimal minimizers, Uφ∗ and X̂φi in the CoordSatCapFus and CoordSatCap algorithms,
i
respectively, is not required.
28 We assume that the value of f (X) for any X ⊆ V can be obtained by
an oracle call and δ refers to the upper bound on the computation time of
this oracle call.

IEEE TRANSACTIONS ON INFORMATION THEORY

maximal/largest minimizers exist [26, Lemma 2.1]. It is shown
in [26, Section 7.1] that the minimal and maximal minimizers
can be determined by the minimum-norm point in the base
polyhedron and the minimum-norm point can be determined
by the SFM algorithm in [43]. It means that the minimal
minimizer of an SFM problem, as required by step 3 in
the CoorSatCap algorithm and step 5 in the CoorSatCapFus
algorithm, can be determined at the same time when the SFM
is solved.
Although the SFM algorithms in [38]–[43] vary in computation complexity, the exact completion time of an SFM
algorithm depends on |V |. We call |V | the size of the SFM
problem min{f (X) : X ⊆ V }. In this section, we study
the complexity of the MDA and SIA algorithms proposed
in Sections V in terms of the size of the SFM problem and
completion time (in seconds), respectively. It should be noted
that, in this paper, we assume that the value of the entropy
function H at a given subset X ⊆ V can be evaluated by an
oracle call, which takes X as an input and outputs H(X), and
δ refers to the complexity upper bound of this oracle call.
1) CoordSatCapFus vs. CoordSatCap: The main subroutine of the MDA and SIA algorithms is the CoordSatCap or
CoordSatCapFus algorithm, and the core part of the CoordSatCap and CoordSatCapFus algorithms is the SFM problem that
determines the saturation capacity ξ̂φi . Consider the CoordSatCap algorithm where the saturation capacity is determined by
min{fα# (X) − r(X) : φi ∈ X ⊆ Vi }.

(18)

The size of this SFM problem is |Vi | − 1. The SFM problem
min{fα# (Ũ )−r(Ũ ) : {φi } ∈ U ⊆ Pi∗ } in the CoordSatCapFus
algorithm is over Pi∗ , a fused user set of Vi , where each
non-singleton subset X ∈ Pi∗ is treated as a super user that
corresponds to one dimension in Pi∗ . Since |Pi∗ |−1 ≤ |Vi |−1,
the computation complexity of the CoordSatCapFus algorithm
is no greater than that of the CoordSatCap algorithm.
Example V.16. For φ3 = 2 in Example V.10, we have P3∗ =
{{4, 5}, {2}}, where {4, 5} forms one dimension in P3∗ , so
that the size of the SFM problem min{fα#(Ũ )−r(Ũ ) : {φ3 } ∈
U ⊆ P3∗ } is |P3∗ | − 1 = |{{4, 5}, {2}}| − 1 = 1. Suppose that
we solve the problem min{fα# (X) − r(X) : φ3 ∈ X ⊆ V3 }
instead. Then, the size of this SFM problem is |V3 | − 1 =
|{2, 4, 5}| − 1 = 2, which is greater than |P3∗ | − 1.
However, the complexity of the CoordSatCapFus algorithm
in the worst case is the same as that of the CoordSatCap
algorithm, which is O(|V |·SFM(|V |)). The worst case is when
Pi∗ = {{φ1 }, . . . , {φi }} for all i ∈ V , which happens when
the components in ZV are mutually independent.
2) MDA algorithm: The MDA algorithm with the CoordSatCapFus being the subroutine completes in O(|V |2 ·
SFM(|V |)) time. We remark that O(|V |2 · SFM(|V |)) is
the complexity upper bound for two reasons. On one hand,
the complexity of the CoordSatCapFus algorithm is upper
bounded by O(|V | · SFM(|V |)); On the other hand, the
number of calls of the CoordSatCapFus algorithm in the MDA
algorithm is upper bounded by |V |. Then, the complexity of
solving the non-asymptotic minimum sum-rate problem in the
finite linear source model by no more than one additional call

·105

MDA by CoordSatCap

8

|V |2 (|V |−1)
2

MDA by CoordSatCapFus

6

|V |

1.9

(|V |−1)
2

4

2

0

10

20

30

40

50

60

70

80

90

100

110

120

|V |
Fig. 11. The results in Experiment V.17. H(V ) is fixed to 50 and the
number of users |V | varies from 5 to 120. MDA by CoordSatCapFus
refers to the MDA algorithm with the CoordSatCapFus algorithm being the
subroutine, while MDA by CoordSatCap refers to the MDA algorithm with
the CoordSatCap algorithm where the saturation capacity is determined by
problem (18) being the subroutine. The sum-size of SFM refers to the total
size of SFM algorithm in one call of the MDA algorithm. The sum-size
averaged over 20 repetitions is presented in this figure. The average sum-size
2
|−1)
of SFM in one call of the MDA algorithm is upper bounded by |V | (|V
.
2

of the CoordSatCapFus algorithm, as proposed in Section V-C,
is upper bounded by O((|V | + 1) · |V | · SFM(|V |)).
Experiment V.17. Let H(V ) be fixed to 50 and the number
of users |V | vary from 5 to 120. For each value of |V |, we
repeat the following procedure for 20 times:
• randomly generate a finite linear source model with the
column vector zi = Ai x for all i ∈ V subject to the
condition l(x) = H(V );
• solve the asymptotic minimum sum-rate problem by applying the MDA algorithm as follows:
– MDA by CoordSatCap: Algorithm 1, where the Dilworth truncation problem in steps 2 and 6 is solved
by the CoordSatCap algorithm with the saturation
capacity determined by (18);
– MDA by CoordSatCapFus: Algorithm 1, where the
Dilworth truncation problem in steps 2 and 6 is
solved by the CoordSatCapFus algorithm.
We sum up the sizes of the SFM algorithm in each run of
the MDA algorithm. This sum-size is averaged over the 20
repetitions and shown in Fig. 11. Note, the average sum-size of
2
|−1) 29
.
the MDA by CoordSatCap is upper bounded by |V | (|V
2
2
|V | (|V |−1)
to
It can be shown that there is a reduction from
2
|V |1.9 (|V |−1)
in
the
average
sum-size
of
the
SFM
problem
by
2
implementing the CoordSatCapFus algorithm. This reduction
could be considerable when |V | is large. For example, in
Fig. 11, when |V | = 25, the average sum-size of SFM is
6037.5 for MDA by CoordSatCap and 3831.4 for MDA by
CoordSatCapFus.
The authors in [45] proposed a divide-and-conquer (DC)
algorithm for solving the asymptotic minimum sum-rate prob29 This refers to the average size of the SFM algorithm in the MDA
algorithm. The computation complexity of the MDA algorithm is still
O(|V |2 · SFM(|V |)).

average completion time in seconds

average sum-size of SFM in MDA

DING et al.: DETERMINING OPTIMAL RATES FOR COMMUNICATION FOR OMNISCIENCE

17

7

SIA by CoordSatCap
4 · 10−3 · |V |1.5
SIA by CoordSatCapFus
4 · 10−3 · |V |1.27

6
5
4
3
2
1
0

10

20

30

40

50

60

70

80

90

100

110

120

|V |
Fig. 12. The results of Experiment V.18. H(V ) is fixed to 50 and the number
of users |V | varies from 5 to 120. SIA by CoordSatCapFus refers to the SIA
algorithm with the CoordSatCapFus algorithm being the subroutine, while SIA
by CoordSatCap refers to the SIA algorithm with the CoordSatCap algorithm
being the subroutine. The run-time in seconds of each call of the SIA
algorithm is recorded and averaged over 20 repetitions. We implemented the
minimum norm algorithm in [43] as the SFM algorithm. The SIA algorithm
is run in MATLAB R2013a.

lem. This algorithm finds the fundamental partition P ∗ and
recursively breaks each element in P ∗ to singletons by calling
the decomposition algorithm (DA) algorithm in [46, Section
3] [33, Algorithm II]. The DC algorithm completes in O(|V |3 ·
SFM(|V |)) time. The detailed description of the DC algorithm
is in Appendix D, where we also show that the recursive
splitting of the subsets in P ∗ is not necessary since the
asymptotic minimum sum-rate problem can be solved at the
same time when the fundamental partition P ∗ is determined.
3) SIA algorithm: The authors in [15, Appendix F] [18,
Section III-C] show that the complexity of adapting the
estimation α on an integer set to the minimum sum-rate
RNCO (V ) in a finite linear source model grows logarithmically in H(V ). Therefore, the SIA algorithm completes in
O(log H(V ) · |V | · SFM(|V |)) time. To show the actual runtime, or completion time in seconds, of the SIA algorithm, we
do the following experiment.
Experiment V.18. Let H(V ) be fixed to 50 and the number
of users |V | vary from 5 to 120. For each value of |V |, we
repeat the following procedure for 20 times:
• randomly generate a finite linear source model with the
column vector zi = Ai x for all i ∈ V subject to the
condition l(x) = H(V );
• solve the non-asymptotic minimum sum-rate problem by
applying the SIA algorithm as follows:
– SIA by CoordSatCap: Algorithm 4, where the Dilworth truncation problem in steps 2 and 5 is solved
by the CoordSatCap algorithm with the saturation
capacity determined by (18);
– SIA by CoordSatCapFus: Algorithm 4, where the
Dilworth truncation problem in steps 2 and 5 is
solved by the CoordSatCapFus algorithm.
We implement the minimum-norm point algorithm proposed in
[43] for solving the SFM problems in the CoordSatCap and
CoordSatCapFus algorithms. The SIA algorithm is written in

18

IEEE TRANSACTIONS ON INFORMATION THEORY

MATLAB and run in MATLAB R2013a. We do the experiment
on a desktop computer with Intel Core i7-3770 processer,
8Gb RAM and 64-bit Windows 7 Enterprise operating system.
The run-time in seconds in each call of the SIA algorithm
is recorded and averaged over repetitions. The results are
shown in Fig. 12. The run-time of SIA by CoordSatCap is
comparable to 4 · 10−3 · |V |1.5 . With the fusion method, SIA
by CoordSatCapFus reduces it to 4 · 10−3 · |V |1.27 .
The authors in [15, Appendix G] show that the SIA by
CoordSatCap method based on the minimum-norm algorithm
[43] completes in 4 · 10−3 · |V |1.85 seconds on average,
which is slower than the result in Experiment V.18. The main
reason that can cause this run-time reduction is that we do
the experiment on a dataset and computer that are different
from those in [15, Appendix G]. In addition, the LB that
we used in the SIA is tighter than the one in [15, Appendix
F] may be another reason that results in a faster run-time.
On the other hand, the complexity of the minimum-norm
algorithm is still unknown and may vary with different data
processing softwares [43]. Therefore, while the average runtime just shows an example on how faster the SIA algorithm
completes in practice, the complexity of the SIA algorithm is
still O(log H(V )·|V |·SFM(|V |)), i.e., no matter how good the
run-time is, it cannot be used to characterise the complexity of
the SIA algorithm. However, based on Figs. 11 and 12, we can
see clearly that the fusion method in CoordSatCapFus algorithm contributes to a considerable reduction in computation
complexity when the number of users |V | grows.
It should be noted that finite linear source model is used in
Experiments V.17 and V.18 since the optimality of the output
rate vector can be verified by random linear network coding
(RLNC) according to [11, Theorem 6]. The results of the MDA
algorithm in Experiment V.17 is checked by packet-splitting
and applying RLNC to the packet chunks.
VI. M INIMUM W EIGHTED S UM - RATE P ROBLEM
The minimum weighted sum-rate problem, the problem of
minimizing a weighted sum-rate in the optimal rate vector
set, has been considered in CO in [15], [18] for the finite
linear source mode. In this section, we show how to solve the
minimum weighted sum-rate problem in the asymptotic and
non-asymptotic models by choosing a proper linear ordering
in the CoordSatCapFus or CoordSatCap algorithm.
|V |
Let wV P
= (wi : i ∈ V ) ∈ R+ be a weight vector and
⊺
wV rV =
i∈V wi ri be the weighted sum-rate of rV . The
minimum weighted sum-rate problem in the asymptotic model
and non-asymptotic models are respectively
∗
min{wV⊺ rV : rV ∈ RACO
(V )},
∗
min{wV⊺ rV : rV ∈ RNCO
(V )}.

We say that Φ = (φ1 , . . . , φ|V | ) is a linear ordering w.r.t. wV
if wφ1 ≤ wφ2 ≤ . . . ≤ wφ|V | . For a given weight vector wV ,
a linear ordering Φ w.r.t. wV can be chosen, for which we
have Theorem VI.1 below. The proof is in Appendix E.
|V |
R+ ,

Theorem VI.1. For a weight vector wV ∈
by fixing Φ
to be the linear ordering w.r.t. wV in the CoordSatCapFus

or CoordSatCap algorithm, the optimal rate rV returned by
the MDA algorithm is the minimizer of min{wV⊺ rV : rV ∈
∗
RACO
(V )}. In the finite linear source model and CCDE, the
optimal rate rV returned by CoordSatCapFus or CoordSatCap
algorithm with input α = RNCO (V ) and linear ordering w.r.t.
∗
wV is the minimizer of min{wV⊺ rV : rV ∈ RNCO
(V )}.
Based on Theorem VI.1, for a finite linear source model,
the minimum weighted sum-rate problem can be solved by
the SIA algorithm if we choose a proper linear ordering in
the CoordSatCapFus or CoordSatCap algorithm. This result is
consistent with the ones in [15], [18]. Note, the SIA algorithm
adapts the sum-rate by starting with a LB that is tighter than
the ones in [15], [18].30
Example VI.2. It can be shown that the optimal rate vector
∗
(V ) determined by the MDA
rV = (1, 12 , 12 , 29 , 0) ∈ RACO
algorithm based on the linear ordering Φ = (4, 5, 2, 3, 1) in
∗
Example V.2 is the minimizer of min{wV⊺ rV : rV ∈ RACO
(V )}
|V |
where wV ∈ R+ could be any weight vector such that w4 ≤
w5 ≤ w2 ≤ w3 ≤ w1 , e.g., wV = (2, 0.85, 1.1, 0.11, 0.13).
∗
The optimal rate vector rV = (0, 1, 1, 5, 0) ∈ RNCO
(V ) based
on the linear ordering Φ = {4, 5, 2, 3, 1} in Examples V.13
∗
and V.15 is the minimizer of min{wV⊺ rV : rV ∈ RNCO
(V )}
|V |
where wV ∈ R+ could be any weight vector such that
w4 ≤ w5 ≤ w2 ≤ w3 ≤ w1 .
|V |

Note, for a weight vector wV ∈ R+ such that all dimensions wi are equal, e.g., wV = 1 = (1, . . . , 1) ∈ R|V | , the
minimum weighted sum-rate problem reduces to the minimum
sum-rate problem. In addition, if the problem is just to
∗
∗
determine an optimal rate vector in RACO
(V ) or RNCO
(V ),
the linear ordering Φ in the CoordSatCap and CoordSatCapFus
algorithms can be arbitrarily chosen.
VII. F UNDAMENTAL PARTITION : M INIMAL S EPARATORS
The fundamental partition P ∗ is not only the optimizer
for the asymptotic minimum sum-rate problem, but also an
essential solution to many problems. In network strength or
optimal attack problems [35]–[37], [47], the fundamental partition is an optimal way for an attacker to disconnect a network,
i.e., decomposing the network into the fundamental partition
requires the least effort on breaking the connections/edges
between nodes. The authors in [46] proposed a novel clustering
criterion, which is called minimum average cost (MAC) clustering, based on the submodularity of the similarity measures
that is generally used in clustering problems. The objective
function in MAC is defined as the clustering cost averaged over
the incremental number of clusters. Based on the MAC, the
authors in [48] proposed an information-theoretic clustering
(info-clustering) framework where the MMI is used as the
similarity measure and the purpose is to search a clustering
solution such that the intra-cluster MMI is maximized while
the inter-cluster MMI is minimized. In both MAC clustering
and info-clustering, the optimal clustering is the fundamental
30 The authors in [15] suggested LB H(V )− min
i∈V H({i}) as the initial
guess of the minimum sum-rate, which is shown to be looser than the one
proposed in Proposition IV. In [15, Algorithms 3], the rate adaptation is done
in the region {0, 1, . . . , H(V )}.

DING et al.: DETERMINING OPTIMAL RATES FOR COMMUNICATION FOR OMNISCIENCE

partition P ∗ . In CO, beyond being the optimizer of the minimum sum-rate problem (7a), the fundamental partition P ∗ has
practical interpretation or usefulness in other aspects. In this
section, we show that P ∗ is the set of the minimal separators of
a submodular function which makes the estimation of the value
of function fˆR#ACO (V ) and the separable convex minimization
∗
problem over RACO
(V ) decomposable.
For a normalized submodular set function f : 2V 7→ R,
a nonempty proper subset X ( V is a separator of f if
f (X) + f (V \ X) = f (V ) [26, Section 3.3].31 A submodular
set function f is called separable if there exists a separator of
f . For each separable submodular set function, there exists a
unique set of minimal separators as defined below.
Definition VII.1 (minimal separators [26, Theorem 3.38]).
For a separable submodular set function f : 2V 7→ R, a
partition P ∈ Π(V ) is the set of minimal separators if, for all
X ∈ P, X is a separator and any X ′ ( X such that X ′ 6= ∅
is not a separator of f .
Theorem VII.2. fˆR#ACO (V ) is a separable submodular function
and the fundamental partition P ∗ is the set of minimal
separators of fˆ#
.
RACO (V )

19

the value of fˆR#ACO (V ) at any subset X ⊆ V into subtasks:
get the values of fˆR#ACO (V ) at C ∩ X for all C ∈ P ∗ and sum
them up. Here, each value of fˆR#ACO (V ) (C ∩X) can be obtained
by applying the CoordSatCap or CoordSatCapFus algorithm.
By doing so, the complexity of evaluating fˆR#ACO (V ) (X) is
reduced from O(|X| · SFM(|X|)) to O(η · SFM(η)) where
η = max{|C ∩ X| : C ∈ P ∗ }. Property (b) means that
a separable submodular function results in a separable base
polyhedron, which gives rise to property (c) [26, Lemma 3.41].
Property (c) is an important result in CO in that it makes the
separable convex minimization problem over the optimal rate
∗
vector set RACO
(V ) decomposable. In the following context,
we first show the examples of properties (a) and (b) and
then discuss the decomposability of the separable convex
minimization problem based on property (c).
Example VII.4. For the system in Example III.11, we know
that the minimum sum-rate RACO (V ) = 13
2 and the fundamental partition P ∗ = {{1, 4, 5}, {2}, {3}} for the asymptotic
model by the MDA algorithm. Consider the value of the
Dilworth truncation function fˆR#ACO (V ) at X = {1, 2, 3, 5}.
Based on property (a) in Lemma VII.3, we have

The proof of Theorem VII.2 is in Appendix F.
A. Properties of Minimal/Finest Separators
For any X, Y ⊆ V such that X ∩ Y = ∅, let rX ⊕ rY =
rX⊔Y be the direct sum of rX and rY . For example, for
r{1,3} = (r1 , r3 ) = (3, 0.7) and r{2,5,6} = (r2 , r5 , r6 ) =
(2.4, 2, 4), r{1,3} ⊕ r{2,5,6} = r{1,2,3,5,6} = (3, 2.4, 0.7, 2, 4).
Lemma VII.3 (properties of minimal separators [26, Theorems 3.32 and 3.38, Lemma 3.37]). For the fundamental
partition P ∗ as the set of minimal separators of fˆR#ACO (V ) ,
the followings hold.
P
(a) fˆR#ACO (V ) (X) = C∈P ∗ fˆR#ACO (V ) (X ∩ C) for all X ⊆ V ;
(b) The dimension of B(fˆR#ACO (V ) , ≤) is |V | − |P ∗ | and
B(fˆR#ACO (V ) , ≤) =
{⊕C∈P ∗ rC : rC ∈ B(fˆR#ACO (V ),C , ≤), C ∈ P ∗ },
where fˆR#ACO (V ),C is the Dilworth truncation of fR#ACO (V ),C ,
the reduction of fR#ACO (V ) on C;
(c) Let rV be any rate vector in B(fˆR#ACO (V ) , ≤). For any
C, C ′ ∈ P ∗ such that C 6= C ′ ,
rV + ǫ(χi − χj ) ∈
/ B(fˆR#ACO (V ) , ≤)
for all ǫ > 0, i ∈ C and j ∈ C ′ .
Based on property (a) in Lemma VII.3, by using the
fundamental partition P ∗ , we can break the task of evaluating
31 In [26, Section 3.3], the author defined the connectivity of a submodular
system that is denoted by two tuple: the power set 2V and the rank function
f : 2V 7→ R that is submodular. (2V , f ) is called connected if there does
not exist a nonempty subset X ( V such that f (X) + f (V \ X) = f (V ).
Then, X is a ‘separator’ if a submodular system is disconnected. The name
‘separator’ is also used in [49, Section 3]. In this paper, without introducing
the concept of the submodular system, we define the separator and separability
w.r.t. a submodular set function.

#
fˆ13/2
({1, 2, 3, 5}) =

X

#
fˆ13/2
({1, 2, 3, 5} ∩ C)

C∈P ∗
#
#
#
= fˆ13/2
({1, 5}) + fˆ13/2
({2}) + fˆ13/2
({3})
1 1
=4+ +
2 2
= 5.

Here, the value of fˆ#
13 ({1, 2, 3, 5}) can be obtained in O(4 ·
2
P
SFM(4)) time, while the value of C∈P ∗ fˆ#
13 ({1, 2, 3, 5}∩C)
2
can be obtained in O(2 · SFM(2)) time. Consider the base
#
polyhedron B(fˆ13/2 , ≤) for the the system in Example III.11.
According to property (b) in Lemma VII.3, the dimension of
#
B(fˆ13/2
, ≤) is |V | − |P ∗ | = 2.
We can visualize property (b) in Lemma VII.3 via Figs. 9
and 10. In Fig. 9, when α = 23
4 and C = {1, 4, 5},
#
fˆα,C
is separable with the minimal separator set being
#
P ∗ = {{1}, {4, 5}} so that the dimension of B(fˆα,C
, ≤)
#
∗
is |C| − |P | = 1, i.e., B(fˆα,C , ≤) is a 1-dimension line
#
segment, and r{4,5} ⊕ r1 ∈ B(fˆ23/4,C
, ≤) for r1 = 34 and
#
all r{4,5} ∈ B(fˆ23/4,{4,5} , ≤). In Fig. 10, when α = 13
2 and
#
C = {1, 4, 5}, fˆα,C
is nonseparable so that the dimension of
#
#
B(fˆ13/2,C
, ≤) is |C|−1 = 2, i.e., B(fˆα,C
, ≤) is a 2-dimension
#
32
polygon on the plane {rC ∈ R|C| : r(C) = fˆ13/2
(C) = 11
2 }.
32 A nonseparable function f : 2V 7→ R can be considered as a separable
function with the minimal separator set being P ∗ = {V } so that, according
to property (b) in Lemma VII.3, the dimension of B(f, ≤) is |V | − 1. Also,
for a nonseparable
function f , there does not exist P ∈ Π′ (V ) such that
P
f (X) =
f
(X
∩ C), ∀X ⊆ V or B(f, ≤) = {⊕C∈P rC : rC ∈
C∈P
B(f, ≤), C ∈ P}. The latter means that if we determine rC ∈ B(fC , ≤)
for all C ∈ P, the direct sum rV = ⊕C∈P rC does not necessarily belong
to B(f, ≤).

20

IEEE TRANSACTIONS ON INFORMATION THEORY

∗
B. Separable Convex Function Minimization over RACO
(V )

We callPg : R|V | 7→ R a separable convex function if
g(rV ) =
i∈V gi (ri ) where gi : R 7→ R is convex for all
i ∈ V . For the minimization problem min{g(rV ) : rV ∈
∗
RACO
(V )} where g is a separable convex function, the local
optimality w.r.t. the elementary transform χi − χj implies
global optimality.
Theorem VII.5 ( [26, Theorem 20.3]). For a separable
convex function g, r∗V is the minimizer of min{g(rV ) : rV ∈
∗
RACO
(V )} if and only if, for all i, j ∈ V and ǫ > 0 such that
∗
∗
(V ),
rV + ǫ(χi − χj ) ∈ RACO
g(r∗V ) ≤ g(r∗V + ǫ(χi − χj )).
Corollary VII.6. For all C ∈ P ∗ , let r∗C be the minimizer of
the separable convex minimization problem min{g(rC ) : rC ∈
B(fˆR#ACO (V ),C , ≤)}. r∗V = ⊕C∈P ∗ r∗C is the minimizer of
∗
min{g(rV ) : rV ∈ RACO
(V )}.
In Corollary VII.6, B(fˆR#ACO (V ),C , ≤) is the projection of
∗
the optimal rate vector set RACO
(V ) = B(fˆR#ACO (V ) , ≤) on
the subset C and rC is the projection of some optimal rate
∗
vector rV ∈ RACO
(V ) on C. The proof of Corollary VII.6
is in Appendix F based on property (c) in Lemma VII.3 and
Theorem VII.5. Based on Corollary VII.6, the minimization
∗
problem min{g(rV ) : rV ∈ RACO
(V )} can be divided to |P ∗ |
minimization problems
min{g(rC ) : rC ∈ B(fˆR#ACO (V ),C , ≤)},

(19)

each of which has a lower dimension than the original one.
On the other hand, there exist many algorithms in the literature that efficiently solve the minimization problem (19),
e.g., the algorithms in [50], [51]. We show an example of
Corollary VII.6 below, where g is a quadratic function.
Example VII.7. For the system in Example III.11, consider
P
r2
∗
(V )}
the quadratic programming min{ i∈V wii : rV ∈ RACO
|V |
33
where wV ∈ R+ is a weight vector. The objective function
P
ri2
i∈V wi is separable convex. For this system, we have
∗
RACO (V ) = 13
2 and P = {{1, 4, 5}, {2}, {3}}.
According to Corollary VII.6, we can determine the minimizers of
X r2
i
min{
: rC ∈ B(fˆR#ACO (V ),C , ≤)}
(20)
wi
i∈C

∗

for all C ∈ P and combine the results by obtaining the direct
sum of them. In fact, we just need to solve the problem (20) for
C = {1, 4, 5} since both B(fˆR#ACO (V ),{2} ) and B(fˆR#ACO (V ),{3} )
are singletons that only contain r2 = 21 and r3 = 21 ,
respectively. For problem (20) when C = {1, 4, 5}, it can
be shown that r∗{1,4,5} = ( 23 , 2, 2) when w{1,4,5} = (1, 1, 1)
and r∗{1,4,5} = (1, 2, 25 ) when w{1,4,5} = (1, 3, 4). ThereP
r2
∗
(V )} is
fore, the minimizer of min{ i∈V wii : rV ∈ RACO
3 1 1
∗
∗
rV = ( 2 , 2 , 2 , 2, 2) when wV = 1 and rV = (1, 12 , 12 , 2, 25 )
when wV = (1, 2, 5, 3, 4).
33 This

quadratic programming problem is also called the resource allocation
problem under submodular constraints in [52], [53].

P
r2
It is shown in [54] that the problem min{ i∈V wii : rV ∈
∗
RACO
(V )} can be solved in O(|V |2 · SFM(|V |)) time, where
|V | = 5 for the system in Example III.11. But, if we compute
the minimizer of (20) for each subset C in the fundamental
partition P ∗ , the problem can be solved in O(η 2 · SFM(η))
time, where η = max{|C| : C ∈ P ∗ } = 3. Therefore, the
separate computation of the minimizer of min{g(rC ) : rC ∈
∗
RACO
(V )} for all C ∈ P ∗ based on Corollary VII.6 reduces
the computation complexity.
In Example VII.7, the minimzer of the quadratic proP
r2
∗
(V )} is
gramming problem min{ i∈V wii : rV ∈ RACO
called the lexicographical optimizer in [55] since it lexicographically dominates any other rate vectors in the sub∗
modular base polyhedron B(fˆR#ACO (V ) , ≤) = RACO
(V ).34
It is also the optimizer of many otherPoptimization probri +wi
∗
: rV ∈
lems in RACO
(V ) [51],
P [57], e.g., min{ i∈V ∗e
∗
w
ln
r
:
r
∈
R
(V
)}
and
RACO
(V
)},
max{
i
i
V
ACO
i∈V
P
∗
min{ i∈V ri log wrii : rV ∈ RACO
(V )}. The authors in [21]
proposed an integral rate P
incremental method for solving
∗
∈ RNCO
(V )},
the fairness problem min{ i∈V ri log ri : rV P
where the objective function is equivalent to i∈V ri log wrii
when w = 1. However,
this method is not able to provide
P
∗
(V )} for the
a solution to min{ i∈V ri log ri : rV ∈ RACO
asymptotic model, since the step size of each increment is
uncertain when the rates are real numbers.
VIII. C ONCLUSION
We proposed the MDA and SIA algorithms for searching
an optimal rate vector that attains omniscience with the minimum sum-rate in the asymptotic and non-asymptotic models,
respectively. We also proposed a fusion method to solve
the Dilworth truncation problem, a subroutine in the MDA
and SIA algorithms, and ran experiment to show that this
fusion method contributes to a reduction in computational
complexity. We showed that the minimum weighted sum-rate
problem in both asymptotic and non-asymptotic models can
be solved by choosing a proper linear ordering in the MDA
and SIA algorithms, respectively. We proved the existence of a
fractional optimal rate vector in the finite linear source model
which can be implemented by (|P ∗ | − 1)-packet-splitting in
CCDE. In addition, we revealed the decomposition property
of the fundamental partition P ∗ in the asymptotic model,
where we showed that the tasks of evaluating the Dilworth
truncation function and minimizing a separable parametric
convex function over the optimal rate vector set can be
decomposed into subtasks so that the overall complexity is
reduced.
To solve a CO problem in practice, there still remains one
problem: What to send in each transmission. It is shown in [18]
that, for an optimal transmission rate vector, the coding scheme
for attaining omniscience in the finite linear source model
can be designed based on a simultaneous matrix completion
algorithm [58], which completes in O(|V |4 ·γ·log(|V |·H(V )))
time with γ denoting the complexity of the matrix rank
34 We refer the reader to [55], [56] for the detailed definition and explanation
of the lexicographical domination and its properties in the submodular base
polyhedron.

10

fˆα# (V ) = minP∈Π(V ) fα# [P]

fˆα#(V ) = minP∈Π(V ) fα# [P]

DING et al.: DETERMINING OPTIMAL RATES FOR COMMUNICATION FOR OMNISCIENCE

P0 = {{1, 2, 3}}

5

P1 = {{1}, {2}, {3}} = P ∗

0

fˆα# (V )
fα# (V ) = α

−5
0

1

2

3

4

5

6

21

P0 = {{1, 2, 3, 4, 5}}

10

P1 = {{1, 4, 5}, {2}, {3}} = P ∗
P2 = {{4, 5}, {1}, {2}, {3}}

0

P3 = {{1}, {2}, {3}, {4}, {5}}

−10

fˆα# (V )
fα# (V ) = α

−20
0

1

function. But, it is still worth discussing if there exists other
less complex algorithms for the coding design.

P RINCIPAL

A PPENDIX A
S EQUENCE OF PARTITIONS (PSP)

We define the pairwise relationship between two partitions
in Π(V ) as follows.
Definition A.1 (order ). For P, P ′ ∈ Π(V ), we denote
′
′
′
′
• P  P if, for all X ∈ P, ∃X ∈ P such that X ⊆ X ;
′
′
′
• P = P if P  P and P  P ;
′
′
′
• P ≺ P if P  P and P 6= P .
In other words, P  P ′ if P is finer than P ′ and
P ≺ P ′ if P is strictly finer than P ′ . For example, for
P = {{1, 2}, {3}, {4}} and P ′ = {{1, 2, 3}, {4}}, we have
P  P ′ . In fact, P ≺ P ′ .
Theorem A.2 (PSP [46, Sections 2.2 and 3]35 , [33, Definition
3.8]). fˆα# (V ) = minP∈Π(V ) fα# [P] is a piecewise linear
nondecreasing curve in α with p ≤ |V | − 1 critical/turning
points
H(V ) = α0 > α1 > α2 > . . . > αp ≥ 0
that have the following properties.
(a) Denote Pj the finest/minimal minimizers of the Dilworth
truncation problem minP∈Π(V ) fα#j [P]. All Pj s form a
partition chain/sequence CP :
{V } = P0 ≻ P1 ≻ . . . ≻ Pp = {{i} : i ∈ V }.
If αj > α > αj+1 for some j ∈ {0, . . . , p − 1}, the
minimizer of minP∈Π(V ) fα# [P] is uniquely Pj ; If α < αp ,
the minimizer is uniquely Pp = {{i} : i ∈ V };
(b) The gradient of fˆα# (V ) is decreasing in α: The gradient
is |Pp | = |V | initially; It changes to |Pj−1 | after each
critical value αj and finally decreases to 1 after α1 .
Corollary A.3. α1 = RACO (V ) and P1 = P ∗ , i.e., the
parameters in PSP that correspond to the first critical point α1
35 The authors in [46] discuss the problem that is called β-minimum average
clustering (β-MAC). It can be shown that the minimum sum-rate problem
considered in this paper is a β-MAC problem when β = 1.

3

4

5

6

7

8

9

10

α

α
Fig. 13. The value of fˆα# (V ) as a function of α for the system in
Example II.1. α1 = RACO (V ) = 27 and P1 = P ∗ = {{1}, {2}, {3}}
according to Corollary A.3.

2

Fig. 14. The value of fˆα# (V ) as a function of α for the system in Example III.11. α1 = RACO (V ) = 13
and P1 = P ∗ = {{1, 4, 5}, {2}, {3}}
2
according to Corollary A.3.

constitute the solutions to the asymptotic minimum sum-rate
problem.
Proof: According to Theorem III.3, the base polyhedron
B(fα# , ≤) is nonempty if and only if α = fˆα# (V ). In other
words, B(fα# , ≤) 6= ∅ if and only if the value of α falls in the
segment of the piecewise linear fˆα# (V ) vs. α curve where the
fˆα# (V ) and fα# (V ) = α overlap, which, based on property (b)
in Theorem A.2, is when α ≥ α1 . Then, the minimum sumrate RACO (V ) is the smallest value of α such that B(fα# , ≤) 6=
∅, which is α1 . All maximizers of (7a) and {V } constitute the
set of all minimizers of minP∈Π(V ) fα#1 [P]. So, the minimal
minimizer P1 is the minimal maximizer of (7a), i.e., P1 equals
to the fundamental partition P ∗ .
The proof of Corollary A.3 is exemplified below.
Example A.4. We show the plot fˆα# (V ) in α for the systems
in Examples II.1 and III.11 in Figs. 13 and 14, respectively.
It can be seen from both figures that fˆα# (V ) is an increasing
piecewise linear function in α. We discuss Fig. 14 based on
Theorem A.2 and Corollary A.3 as follows.
In addition to α0 and P0 , there are three critical points αj
with Pj , the minimal minimizers of minP∈Π(V ) fα#j [P], being
α0 = 10, P0 = {{1, 2, 3, 4, 5}};
13
, P1 = {{1, 4, 5}, {2}, {3}};
α1 =
2
α2 = 6,
P2 = {{4, 5}, {1}, {2}, {3}};
α3 = 4,

P3 = {{1}, {2}, {3}, {4}, {5}}.

We have the partition sequence CP : P0 ≻ P1 ≻ P2 ≻ P3 . The
gradient is: 5 when α ∈ [0, α3 ]; 4 when α ∈ [α3 , α2 ]; 3 when
α ∈ [α2 , α1 ]; 1 when α ∈ [α1 , α0 ]. In addition, one can show
that the minimizer of minP∈Π(V ) fα# [P] is uniquely P3 when
α ∈ [0, α3 ), P2 when α ∈ (α3 , α2 ), P1 when α ∈ (α2 , α1 )
and P0 when α ∈ (α1 , α0 ]. Here, α1 and P1 coincide with
the minimum sum-rate RACO (V ) = 13
2 and the fundamental
partition P ∗ = {{4, 5}, {1}, {2}, {3}} in Example III.11,
respectively.
In Fig. 14, we also plot the line fα# (V ) = α. It can be seen
that fα# (V ) overlaps with fˆα# (V ), i.e., α = fˆα# (V ), when
α ∈ [α1 , α0 ]. So, B(fα# , ≤) 6= ∅ when α ≥ α1 . According to

22

IEEE TRANSACTIONS ON INFORMATION THEORY

Theorem III.3, α1 = 13
2 , the minimal value of α in the region
[α1 , α0 ], is the minimum sum-rate RACO (V ).
Consider the region when α < α1 = 13
2 in Fig. 14. We
have fα# (V ) = α > fˆα# (V ). As discussed in Section III-C, the
polyhedron P (fα# , ≤) does not intersect with the hyperplane
{rV ∈ R|V | : r(V ) = α}, i.e., B(fα# , ≤) = ∅, in this region.
It means that the minimum sum-rate α is too low for attaining
the omniscience in V . On the contrary, when α ≥ α1 = 13
2 ,
P (fα# , ≤) intersects with the hyperplane {rV ∈ R|V | : r(V ) =
α}, i.e., B(fα# , ≤) = ∅. It can be seen that the PSP provides
another interpretation of Theorem III.3.
A. Proof of Theorem V.1
We have the following properties for ϕ and the partitions
Pj s in the PSP.
Lemma A.5 (property of ϕ(P) [33, Theorem 3.14], [46,
Section 3]). The followings hold for ϕ(P) and Pj ∈ CP in
the PSP for j ∈ {1, . . . , p}.
(a) α1 = ϕ(P1 );
(b) For any j such that 1 < j ≤ p, let α = ϕ(Pj ). Then,
αj < α < α1 .
Based on Lemma A.5 and Theorem A.2, consider two
situations for a partition Pj ∈ CP where j ∈ {1, . . . , p}:
• If j = 1, then α1 = ϕ(Pj );
• If j > 1, then α = ϕ(Pj ) satisfies αj < α < α1 . Let Pj ′
be the minimal minimizer of minP∈Π(V ) fα# [P]. Then,
P1 ≻ Pj ′ ≻ Pj .
They suggest a recursive method for determining P1 and α1 .
Consider the iteration
α(n+1) = ϕ(P (n) ),
where P (n) is the minimal minimizer of minP∈Π(V ) fα#(n) [P].
Let the iteration start with α(0) ≤ α1 and terminate when
α(n+1) = α(n) . We necessarily have {α(n) } and {P (n) } converge to α1 and P1 , respectively. Let the recursion terminate
at N th iteration, where we have α(N +1) = α(N ) . Here, N ≤
|V | − 1 necessarily since, according to Theorem A.2, we have
at most |V | − 1 critical values. According to Lemma A.5(b),
α(n+1) > α(n) and P (n+1) ≻ P (n) for all n ∈ {0, . . . , N }.
Recall that α1 = RACO (V ) and P1 = P ∗ (Corollary A.3).
The MDA algorithm exactly implements the recursion above
with α initiated as the LB on RACO (V ) in Proposition IV.1.
Therefore, Theorem V.1 holds.
The authors in [46, Section 3] [33, Algorithm II] proposed
a decomposition algorithm (DA) for determining all partitions
Pj s and the corresponding critical values αj s in the PSP. The
MDA algorithm can be considered as an adapted version of
the DA algorithm for determining just P1 and α1 . Hence the
name MDA.

T IGHT

A PPENDIX B
S ETS AND P ROOF OF O PTIMALITY
C OORD S AT C AP A LGORITHM

OF

According to Lemma III.2, fα# : 2V 7→ R is an intersecting
submodular set function for all α ∈ R+ . In addition, fα#

is normalized, i.e., fα# (∅) = 0, and P (fα# , ≤) = P (fˆα# , ≤)
[26, Theorems 2.5(i) and 2.6(i)] where fˆα# is submodular [31,
Theorem 12.2.4], [46, Theorem 7]. Consider the maximum
sum-rate problem
max{r(V ) : rV ∈ P (fα# , ≤)}
= max{r(V ) : rV ∈ P (fˆα# , ≤)}. (21)
The maximizers of max{r(V ) : rV ∈ P (fˆα# , ≤)} form the
base polyhedron B(fˆα# , ≤) [26, Theorem 2.3]. Then, problem
(21) is solved if a rate vector rV ∈ B(fˆα# , ≤) is determined.
On the other hand, there is a relationship between (21) and
the Dilworth truncation problem [37, Theorem 3.1]36 :
max{r(V ) : rV ∈ P (fα# , ≤)} = min fα# [P].
P∈Π(V )

B(fˆα# , ≤),

Then, for a rate vector rV ∈
its sum-rate r(V ) also
determines the value of fˆα# (V ) = minP∈Π(V ) fα# [P].
Consider the CoordSatCap algorithm, which is originally
proposed as Greedy Algorithm II in [26, Section 3.2]. Since
the algorithm starts with a rate vector rV ∈ P (fα# , ≤), it
can be shown by induction that, we have rV ∈ P (fα# , ≤)
and rV + ξ̂φi χφi ∈ P (fα# , ≤) for all i ∈ {1, . . . , |V |} (also
refer to [26, proof of Theorem 3.19]). Since CoordSatCap
algorithm outputs a point rV ∈ B(fˆα# , ≤) [26, Theorem 3.19],
we finally have a rate vector rV ∈ P (fα# , ≤) with saturation
reached in each dimension, i.e., for all i ∈ {1, . . . , |V |}
/ P (fα# , ≤) [26, Theorem 2.3]. It
and ǫ > 0, rV + ǫχφi ∈
#
means rV ∈ B(fˆα , ≤) with the sum-rate r(V ) being the
maximum of max{r(V ) : rV ∈ P (fα# , ≤)} or the minimum of
minP∈Π(V ) fα# [P]. The minimizer of minP∈Π(V ) fα# [P] can
be determined by the minimizers X̂φi for all i as follows.
Let X̂φi be the minimizer of the saturation capacity problem
min{fα# (X) − r(X) : φi ∈ X ⊆ V } for i ∈ {1, . . . , |V |} in
the CoordSatCap algorithm. For i, let rV be the rate vector
after executing rV ← rV + ξˆφi χφi . Then, X̂φi is rV -tight,
i.e., r(X̂φi ) = fα# (X̂φi ) [26, proof of Theorem 3.19]. At the
end of the CoordSatCap algorithm, we have rV ∈ B(fˆα# , ≤)
and it can be shown by induction that X̂φi is rV -tight for
all i ∈ {1, . . . , |V |}. Due to the intersecting submodularity of
fα# , X̂φi s satisfy property: If X̂φi ∩ X̂φj 6= ∅ for i 6= j, then
X̂φi ∩ X̂φj and X̂φi ∪ X̂φj are also rV -tight [37, Section 3],
[46, Section 4.2], [15, Lemma 6]. Then, consider the following
process:
∗
• Let P ← {X̂φi : i ∈ V };
∗
• Repeatedly merge any two elements X̂φi , X̂φj ∈ P such
∗
∗
that X̂φi ∩ X̂φj 6= ∅, i.e., do P ← (P \ {X̂φi , X̂φj }) ⊔
{X̂φi ∪ X̂φj }, until there are no such elements left.
Since φi ∈ X̂φi for all i ∈ {1, . . . , |V |}, we finally have P ∗
being a partition of V , i.e. P ∗ ∈ Π(V ) and each element in
P ∗ is rV -tight, i.e., r(C) = fα# (C), ∀C ∈ P ∗ . Then, r(V ) =
36 In [37], Theorem 3.1 is based on the polyhedron P ′ (g ′ , ≤) = {r
V ∈
α
′ (X), ∀X ⊆ V, X 6= ∅} with the submodular function
R|V | : r(X) ≤ gα
′ (X) = α − H(V ) + H(X), ∀X ⊆ V , a similar approach as in [15,
gα
′ is not normalized.
Section III-E] that is explained in Remark III.6. Note, gα
′ , ≤), since r(∅) = 0
Therefore, it is easy to verify that P (fα# , ≤) = P ′ (gα
always, and the maximum and maximizers of max{r(V ) : rV ∈ P (fα# , ≤)}
′ , ≤)} coincide.
and max{r(V ) : rV ∈ P ′ (gα

DING et al.: DETERMINING OPTIMAL RATES FOR COMMUNICATION FOR OMNISCIENCE

r(C) = r[P ∗ ] = fα# [P ∗ ]. Recall that rV ∈ B(fˆα# , ≤)
at the end of the CoordSatCap algorithm, which means
P

C∈P ∗

r[P ∗ ] = max{r(V ) : rV ∈ P (fα# , ≤)} = min fα# [P].
P∈Π(V )

Then, P ∗ is a minimizer of minP∈Π(V ) fα# [P] and P ∗ is
the minimal minimizer if X̂φi is the minimal minimizer of
min{fα# (X) − r(X) : φi ∈ X ⊆ V } for all i ∈ {1, . . . , |V |}.
The process above is equivalent to steps 6 and 7 in the
CoordSatCap algorithm. There is another explanation of the
optimality of the CoordSatCap algorithm in [46, Section 4.2].
A. Edmond Greedy Algorithm
It is shown in [26, Theorem 3.18] that, for a normalized
submodular set function f , the CoordSatCap algorithm reduces
to the Edmond greedy algorithm [25]: for i = 1 to |V |, do
rφi = f (Vi ) − f (Vi−1 ),
where Vi = {φ1 , . . . , φi } and V0 = ∅. The resulting rV is
a point in B(f, ≤) [26, Corollary 3.17]. The Edmond greedy
algorithm is modified as: For i = 1 to |V |, do
rφi ← rφi + min{f (X) − r(X) : φi ∈ X ⊆ Vi }
for solving the non-asymptotic minimum sum-rate problem in
the finite linear source model and CCDE in [15], [18], which
is exactly the CoordSatCap algorithm based on Lemma V.6.
B. Proof of Lemma V.3
Since the entropy function H is a polymatroid rank function
[24], we have 0 ∈ P (H, ≤), i.e., 0 ≤ H(X), ∀X ⊆ V .
Consider the rate vector rV = (α − H(V ))χV . For 0 ≤ α ≤
H(V ), we have α − H(V ) ≤ 0. Then, for X = ∅, we have
r(∅) = 0 = fα# (∅); for all X ⊆ V such that X 6= ∅, we have
r(X) = (α − H(V ))|X|
≤ α − H(V )
≤ α − H(V ) + H(X) = fα# (X)
So, rV = (α − H(V ))χV ∈ P (fα# , ≤).
C. Proof of Lemma V.6
Recall that the entropy function H is monotonic [24], i.e.,
H(X) ≤ H(Y ), ∀X, Y ⊆ V : X ⊆ Y . Then, fα# (X) ≤
fα# (Y ), ∀X, Y ⊆ V : ∅ 6= X ⊆ Y . If rV ∈ P (fα# , ≤) such
that ri ≤ 0, ∀i ∈ V initially, we have
fα# (X) − r(X) − (fα# (X ∩ Vi ) − r(X ∩ Vi )) =
fα# (X) − fα# (X ∩ Vi ) − r(X \ (X ∩ Vi )) ≥ 0

also the minimizer of min{fα#(X) − r(X) : φi ∈ X ⊆ V }.37
Therefore, if X̂φi is the minimal minimizer of min{fα#(X) −
r(X) : φi ∈ X ⊆ Vi }, it is also the minimal minimizer of
min{fα# (X) − r(X) : φi ∈ X ⊆ V }.
D. Proof of Lemma V.7
For all i ∈ {1, . . . , |V |}, we have r(C) = fα# (C), ∀C ∈
P : |C| > 1 in the CoordSatCap algorithm (due to the previous updates of rV and rV -tightness as stated in Appendix B)
and, since rV ∈ P (fα# , ≤), r(C ′ ) + fα# (C \ C ′ ) ≥ r(C ′ ) +
r(C \C ′ ) = fα# (C), i.e., r(C ′ ) ≥ fα# (C)−fα# (C \C ′ ), ∀C ′ (
C : C ′ 6= ∅, |C| > 1.
For any X ⊆ V , let Y = {C ∈ P ∗ : C ∩ X 6= ∅}. We have
∗

fα# (X) − r(X) − fα# (Ỹ) + r(Ỹ)
= fα# (X) − fα# (Ỹ) + r(Ỹ \ X)
X
= fα# (X) − fα# (Ỹ) +
r(C \ (C ∩ X))
C∈Y

≥

fα# (X)

−

fα# (Ỹ)

+

X

C∈Y


fα# (C) − fα# (C ∩ X) ≥ 0,

where the last inequality is due to the intersecting submodularity of fα# . The minimality of Ũi∗ over all X ⊆ V such that
φi ∈ X and X̃ = Ũi∗ can be proved by the induction below.
Consider the set X = {C ∈ P ∗ : C ∩ X̂φi 6= ∅}. For all
C ∈ X : |C| = 1, we have C ⊆ X̂φi and r(C ∪ X̂φi ) + ξ̂φi =
r(X̂φi ) + ξˆφi = fα# (X̂φi ); For all C ∈ X : |C| > 1, we
have r(C) = fα# (C) and r(X̂φi ) + ξˆφi = fα# (X̂φi ) so that
r(C ∪ X̂φi ) + ξ̂φi = fα# (C ∪ X̂φi ) (This is also due to the
rV -tightness as stated in Appendix B). By induction, we have
r(X˜ )+ ξˆφi = fα# (X˜) and X̃ = Ũφ∗i , where Ũφ∗i is the minimal
minimizer of min{fα# (Ũ ) − r(Ũ ) : U ⊆ P ∗ , φi ∈ Ũ }.
E. Fundamental Partition P ∗ noncrossing X̂φi
For α ∈ [0, RACO (V )],38 let X̂φi be the minimal minimizer
of min{fα# (X) − r(X) : φi ∈ X ⊆ V } that is non-singleton.
According to Theorem A.2(a), the minimal minimizer of
minP∈Π(V ) fα# [P] must be a Pj for some j ∈ {1, . . . , p} in
the PSP and, according to Appendix B, Pj must be a multiway cut that does not cross X̂φi . We also have α ≥ fα# [Pj ]
which is equivalent to α ≤ ϕ(Pj ). For a P that is crossing
X̂φi , we have fα# [Pj ] < fα# [P], which is equivalent to
ϕ(P) < (1 − θ)α + θϕ(Pj ) ≤ ϕ(Pj ),
|P |−1

j
. It means that for any partition P that
where θ = |P|−1
is crossing X̂φi there always exist a partition Pj for some
j ∈ {1, . . . , p} in the PSP that is not crossing X̂φi such that
ϕ(P) < ϕ(Pj ). Since Pj  P1 = P ∗ for all j ∈ {1, . . . , p},
the fundamental partition does not cross X̂φi , necessarily.

Let rV be any rate vector in ∈ P (fα# , ≤). The following property
can be shown by the intersecting submodularity of fα# [37, Section 3], [46,
Section 4.2], [15, Lemma 6]: If X̂ and Ŷ are two distinctive minimizers of
min{fα# (X) − r(X) : φi ∈ X ⊆ V }, then X̂ ∩ Ŷ and X̂ ∪ Ŷ are also
the minimizers of min{fα# (X) − r(X) : φi ∈ X ⊆ V }. Note, this property
is the same as the tight set argument in Appendix B for the proof of the
optimality of the CoordSatCap algorithm.
38 In the MDA algorithm, we always have α ∈ [0, R
ACO (V )].
37

holds for all X ⊆ V such that φi ∈ X. Therefore, equality
(15) holds for all i ∈ {1, . . . , |V |}. Let X̂ be a minimizer of
min{fα# (X) − r(X) : φi ∈ X ⊆ Vi }. Due to the intersecting
submodularity of fα# , whenever there is a minimizer Ŷ of
min{fα# (X) − r(X) : φi ∈ X ⊆ V } such that Ŷ * Vi , we
have Ŷ ∩ X̂ ⊆ Vi and φi ∈ Ŷ ∩ X̂ 6= ∅. So, Ŷ ∩ X̂ is

23

24

IEEE TRANSACTIONS ON INFORMATION THEORY

A PPENDIX C
T HEOREM V.11 AND C OROLLARY V.14
According to Theorem III.8, fˆα# is a polymatroid rank
function for all α ≥ RACO (V ). In this case, we have B(fˆα# , ≤
|V |
) ⊆ R+ so that 0 ≤ r′V , ∀r′V ∈ EX(fˆα# ) [26, Lemma 3.23].
Based on Lemma V.3, for all α ≤ H(V ), if we start with a rate
vector rV ≤ 0 ≤ r′V , ∀r′V ∈ EX(fˆα# ), we necessarily have
rV ∈ EX(fˆα# ) at the output of the CoordSatCap algorithm.
This proves Theorem V.11. A similar proof can be found in
[46, Section 4.2].
As explained in Appendix B, for a given value of α ≥ 0,
the CoordSatCap algorithm outputs rV ∈ B(fˆα# , ≤), where
the sum-rate r(V ) = fˆα# (V ) = minP∈Π(V ) fα# [P]. According
Theorem III.3, we have r(V ) = α being the necessary
and sufficient condition for a sum-rate α to be achievable.
Also, if α is achievable, we have the output rate vector
rV ∈ B(fα# , ≤) = B(fˆα# , ≤) = {rV ∈ RCO (V ) : r(V ) = α}.
Since the CoordSatCap and CoordSatCapFus algorithms return
the same results, corollary also holds for the CoordSatCapFus
algorithm. This proves Corollary V.14.
P ROOFS

A PPENDIX D
D IVIDE - AND - CONQUER (DC) A LGORITHM [45]
The authors in [45] proposed a divide-and-conquer (DC)
algorithm (as shown in Algorithm 5) for solving the asymptotic minimum sum-rate problem based on the results as
∗
follows. For a subset X ⊆ V , let RACO (X) and PX
be the
minimum sum-rate and the fundamental partition, respectively,
for the asymptotic minimum sum-rate problem for attaining
the omniscience in X. Then, for all optimal rate vectors rX ∈
∗
RACO
(X), we have r(C) = RACO (X)− H(X)− H(C), ∀C ∈
∗
∗
PX [45, Lemma 1].39 Then, for all C ∈ PX
such that |C| = 1,
the optimal rate of the only user in C is determined; for
∗
all C ∈ PX
such that |C| > 1, the optimal rate can be
determined by recursively solving the omniscience problem in
C. Therefore, by knowing the fundamental partition P ∗ for the
∗
omniscience in V , an optimal rate vector in RACO
(V ) can be
solved by recursively breaking the non-singleton subset in the
P ∗ until the rates of all individual users are determined. This
idea is implemented by the DC algorithm, where RACO (X)
∗
and PX
are determined by the DA algorithm in [46, Section
3]. In step 3 in the DC algorithm, ∆r is the excessive rate,
the additional rate that should be transmitted by X in addition
to RACO (V ). ∆r can be transmitted by any users in X after
the omniscience is attained in X [45, Lemma 3].
Example D.1. By applying the DC algorithm to the system in Example III.11, we first determine that the minimum sum-rate RACO (V ) = 13
2 and fundamental partition
P ∗ = {{1, 4, 5}, {2}, {3}}. We also know that we must
1
1
have r({1, 4, 5}) = 11
2 , r({2}) = 2 and r({3}) = 2 for
attaining the omniscience in V with the minimum sum-rate
RACO (V ) = 13
2 . By recursively calling the DC algorithm,
the individual rates in {1, 4, 5} are determined as r1 = 1,
#
RACO (X) − H(X) + H(C) corresponds to fR
(C) =
ACO (V )
RACO (V ) − H(V ) + H(C) in that X is the ground set for the omniscience
problem in X.
39 Here,

Algorithm 5: divide-and-conquer (DC) algorithm [45]

OF

input : a subset X ⊆ V , and r(X) if X 6= V
∗
output: a rate vector rX ∈ RACO
(X)
1
2
3
4

∗
(RACO (X), PX
) ← DA(∅, X);
∗
forall C ∈ PX do r(C) ← RACO (X) − H(X) + H(C);
∗
if X 6= V then ∆r ← r(X) − RACO (X), choose any C ∈ PX
and let r(C) ← r(C) + ∆r;
∗
forall C ∈ PX
: |C| > 1 do rC ← DC(C, r(C));

r4 = 25 and r5 = 0 so that we have the optimal rate vector
∗
(V ) at the output.
rV = (1, 21 , 12 , 25 , 0) ∈ RACO
Since the DA algorithm completes in O(|V |2 · SFM(|V |))
time [46, Theorem 5], the complexity of the DC algorithm is
O(|V |3 · SFM(|V |)). However, the recursive splitting of the
non-singleton subset in the fundamental partition P ∗ in the
DC algorithm is not necessary since an optimal rate vector
∗
rV ∈ RACO
(V ) is obtained when P ∗ is determined by the
DA algorithm.40

P ROOF

A PPENDIX E
OF T HEOREM VI.1

According to Theorem V.11, the MDA algorithm returns an
∗
optimal rate vector rV ∈ RACO
(V ) that is an extreme point
#
ˆ
in B(fRACO (V ) , ≤), i.e., rV ∈ EX(fˆR#ACO (V ) ). Based on [26,
Corollary 3.17], for linear ordering w.r.t. wV , the output rV
∗
is also the minimizer of min{wV⊺ rV : rV ∈ RACO
(V )}, where
#
∗
ˆ
RACO (V ) = B(fRACO (V ) , ≤). It is shown in the proof of Corollary V.12 that, for a finite linear source model, when the input
α = RNCO (V ), the CoordSatCapFus algorithm outputs a rate
vector rV ∈ EX(fˆR#NCO (V ) ), which, according to [26, Corollary
∗
3.17] is the minimizer of min{wV⊺ rV : rV ∈ RNCO
(V )}
#
∗
where RNCO
(V ) = B(fˆRNCO (V ) , ≤). Since the outputs of the
CoordSatCapFus and CoordSatCap algorithms are the same,
it also applies to the CoordSatCap algorithm.

P ROOFS

OF

A PPENDIX F
T HEOREM VII.2 AND C OROLLARY VII.6

The proof of Theorem VII.2 relies on the method for
determining the minimal separators of a submodular function
that is proposed in [26, Lemma 3.41] [49, Theorems 3.1 and
3.2].41
Lemma F.1 ( [26, Lemma 3.41]). For any rate vector
rV ∈ B(fˆR#ACO (V ) , ≤), let X̂i be the minimal minimizers of
min{fˆR#ACO (V ) − r(X) : i ∈ X ⊆ V }. Initiate the minimal
∗
40 In fact, the DC algorithm utilizes R
ACO (V ) and P determined by the
DA algorithm in [46, Section 3] while discards the optimal rate vector rV ∈
#
B(fˆR
, ≤). This is not surprising since the study in [46] aims to solve
ACO (V )
a clustering problem, where the optimal partition P ∗ is of the most interest.
#
Therefore, although a rate vector rV ∈ B(fˆR
, ≤) is returned as an
ACO (V )
auxiliary result, it is not explicitly stated in [46] that B(fˆ#
, ≤) =
RACO (V )

∗ (V ) so that this rate vector is the solution to the asymptotic minimum
RACO
sum-rate problem.
41 This method was first proposed in [49, Theorems 3.1 and 3.2] for
polymatroid rank functions and then generalized to [26, Lemma 3.41] for
submodular functions. Here, the minimal separators also correspond to the
principal structure of a submodular system in [59].

DING et al.: DETERMINING OPTIMAL RATES FOR COMMUNICATION FOR OMNISCIENCE

25

minimizer set P ∗ = {X̂i : i ∈ V } and repeatedly merge any
two distinctive elements X̂i , X̂j ∈ P ∗ such that X̂i ∩ X̂j 6= ∅,
i.e., do P ∗ ← (P ∗ \ {X̂i , X̂j }) ⊔ {X̂i ∪ X̂j }, until there are
no such elements left. The resulting P ∗ is the set of minimal
separators of fˆR#ACO (V ) .

g(r∗V + ǫ(χi − χj )) for all i, j ∈ V and ǫ > 0 such that
∗
rV + ǫ(χi − χj ) ∈ B(fˆR#ACO (V ) , ≤) = RACO
(V ). Therefore,
∗
according to Theorem VII.5, rV = ⊕C∈P ∗ r∗C is the minimizer
∗
of min{g(rV ) : rV ∈ B(fˆR#ACO (V ) , ≤) = RACO
(V )}.

Lemma F.2. Let Φ be any linear ordering of V . For all α ∈
R+ , i ∈ {1, . . . , |V |} and rV ∈ P (fα# , ≤), if ξ̂φi and X̂φi
are the minimum and minimal minimizer of min{fα# (X) −
r(X) : φi ∈ X ⊆ V }, respectively, then ξ̂φi and X̂φi are
also the minimum and minimal minimizer of min{fˆα# (X) −
r(X) : φi ∈ X ⊆ V }, respectively.

R EFERENCES

Proof: Let r′V = rV + ξˆφi χφi . Then, we have r′V ∈
and X̂φi is r′V -tight, i.e., fα# (X̂φi ) = r′ (X̂φi )
[26, proof of Theorem 3.19]. Since P (fα# , ≤) = P (fˆα# , ≤),
r′V ∈ P (fˆα# , ≤) and we have r′ (X̂φi ) ≤ fˆα# (X̂φi ) [26,
Theorems 2.5(i) and 2.6(i)]. On the other hand, fˆα# (X) ≤
fα# (X) for all X ⊆ V by the definition of the Dilworth
truncation. Then, fˆα# (X̂φi ) ≤ fα# (X̂φi ) = r′ (X̂φi ). Therefore,
r′ (X̂φi ) = fˆα# (X̂φi ), which means ξ̂φi is also the minimum
of min{fˆα#(X) − r(X) : φi ∈ X ⊆ V }.
We prove that X̂φi is the minimal minimizer of
min{fˆα# (X)−r(X) : φi ∈ X ⊆ V } by contradiction. Assume
that X̂φi is not the minimal minimizer, i.e., there exists
X ( X̂φi such that φi ∈ X and fˆα# (X) − r(X) = ξ̂φi .
Then, r′ (X) = fˆα# (X) < fα# (X), where the last inequality
is strict due to the fact that X is not the minimizer of
min{fα# (X) − r(X) : φi ∈ X ⊆ V }. According to the
definition of the Dilworth truncation, fˆα# (X) < fα# (X) means
that there exists a P ∗ ∈ Π′ (X) such that

P (fα# , ≤)

r′ (X) = fˆα# (X) = fα# [P ∗ ] = r′ [P ∗ ].
On one hand, we have r′ (C) ≤ fα# (C), ∀C ∈ P ∗ since
r′V ∈ P (fα# , ≤). On the other hand, fα# (C) − r′ (C) =
P
′
′
#
′
′
#
C ′ ∈P ∗ \{C} (r (C ) − fα (C )) ≤ 0, i.e., r (C) ≥ fα (C)
∗
′
#
for all C ∈ P . Then, r (C) = fα (C) for all C ∈ P ∗ .
Let Ĉ ∈ P ∗ such that φi ∈ Ĉ. We have fα# (Ĉ) = r′ (Ĉ),
i.e., fα# (Ĉ) − r(Ĉ) = ξ̂φi . Here, Ĉ ( X necessarily, which
means X̂φi is not the minimal minimizer of min{fα#(X) −
r(X) : φi ∈ X ⊆ V }. This contradicts the given condition.
Therefore, we must have X̂φi being the minimal minimizer of
min{fˆα# (X) − r(X) : φi ∈ X ⊆ V }.
Recall that we have rV ∈ B(fˆR#ACO (V ) , ≤) and the fundamental partition P ∗ at the output of the CoordSatCap
algorithm by inputting α = RACO (V ). For the base point
rV ∈ B(fˆR#ACO (V ) , ≤), X̂i is the minimal minimizer of
min{fˆR#ACO (V ) (X) − r(X), i ∈ X ⊆ V } for all i ∈ V
according to Lemma F.2. If we implement the method in
Lemma F.1 over all X̂i s, we have the set of minimal separators
of fˆR#ACO (V ) the same as the fundamental partition P ∗ . This
proves Theorem VII.2.
Corollary VII.6 is proved as follows. For all C ∈ P ∗ ,
g(r∗C ) ≤ g(r∗C + ǫ(χi − χj )), ∀i, j ∈ C according to Theorem VII.5. On the other hand, according to property (c) in
Lemma VII.3, if i ∈ C and i ∈ C ′ for any C, C ′ ∈ P ∗
such that C 6= C ′ , rV + ǫ(χi − χj ) ∈
/ B(fˆR#ACO (V ) , ≤
∗
) = RACO (V ) for all ǫ > 0. Then, we have g(r∗V ) ≤

[1] N. Ding, C. Chan, Q. Zhou, R. A. Kennedy, and P. Sadeghi, “A faster
algorithm for asymptotic communication for omniscience,” in Proc.
IEEE Globecom Workshop Network Coding Appl., Washington, D.C.,
2016, pp. 1–6.
[2] N. Ding, R. A. Kennedy, and P. Sadeghi, “Estimating minimum sum-rate
for cooperative data exchange,” in Proc. IEEE Int. Symp. Inf. Theory,
Hong Kong, China, 2015, pp. 2618–2622.
[3] N. Ding, C. Chan, T. Liu, R. A. Kennedy, and P. Sadeghi, “A gametheoretic perspective on communication for omniscience,” in Proc. 2016
Australian Commun. Theory Workshop, Melbourn, Australia, 2016, pp.
95–100.
[4] I. Csiszár and P. Narayan, “Secrecy capacities for multiple terminals,”
IEEE Trans. Inf. Theory, vol. 50, no. 12, pp. 3047–3061, Dec. 2004.
[5] S. Nitinawarat and P. Narayan, “Perfect omniscience, perfect secrecy,
and steiner tree packing,” IEEE Trans. Inf. Theory, vol. 56, no. 12, pp.
6490–6500, Dec. 2010.
[6] C. Chan, “Linear perfect secret key agreement,” in Proc. IEEE Inf.
Theory Workshop, Paraty, Brazil, 2011, pp. 723–726.
[7] C. Chan, Al-Bashabsheh, Q. Zhou, N. Ding, T. Liu, and A. Sprintson,
“Successive omniscience,” IEEE Trans. Inf. Theory, vol. 62, no. 6, pp.
3270–3289, Apr. 2016.
[8] S. El Rouayheb, A. Sprintson, and P. Sadeghi, “On coding for cooperative data exchange,” in Proc. IEEE Inf. Theory Workshop, Cairo, Egypt,
2010, pp. 1–5.
[9] T. Courtade and R. Wesel, “Efficient universal recovery in broadcast networks,” in Proc. Annu. Allerton Conf. Commun., Control, and Comput.,
Monticello, IL, 2010, pp. 1542–1549.
[10] T. Courtade, B. Xie, and R. Wesel, “Optimal exchange of packets for
universal recovery in broadcast networks,” in Proc. Military Commun.
Conf., San Jose, CA, 2010, pp. 2250–2255.
[11] A. Sprintson, P. Sadeghi, G. Booker, and S. El Rouayheb, “A randomized algorithm and performance bounds for coded cooperative data
exchange,” in Proc. IEEE Int. Symp. Inf. Theory, Austin, TX, 2010, pp.
1888–1892.
[12] D. Ozgul and A. Sprintson, “An algorithm for cooperative data exchange
with cost criterion,” in Proc. Inf. Theory Appl. Workshop, La Jolla, CA,
2011, pp. 1–4.
[13] N. Abedini, M. Manjrekar, S. Shakkottai, and L. Jiang, “Harnessing
multiple wireless interfaces for guaranteed QoS in proximate P2P
networks,” in Proc. IEEE Int. Conf. Commun. China, Beijing, China,
2012, pp. 18–23.
[14] T. Courtade and R. Wesel, “Weighted universal recovery, practical
secrecy, and an efficient algorithm for solving both,” in Proc. Annu.
Allerton Conf. Commun., Control, and Comput., Monticello, IL, 2011,
pp. 1349–1357.
[15] ——, “Coded cooperative data exchange in multihop networks,” IEEE
Trans. Inf. Theory, vol. 60, no. 2, pp. 1136–1158, Feb. 2014.
[16] S. Tajbakhsh, P. Sadeghi, and R. Shams, “A generalized model for cost
and fairness analysis in coded cooperative data exchange,” in Proc. Int.
Symp. Network Coding, Beijing, China, 2011, pp. 1–6.
[17] D. Slepian and J. Wolf, “Noiseless coding of correlated information
sources,” IEEE Trans. Inf. Theory, vol. 19, no. 4, pp. 471–480, Jul.
1973.
[18] N. Milosavljevic, S. Pawar, S. E. Rouayheb, M. Gastpar, and K. Ramchandran, “Efficient algorithms for the data exchange problem,” IEEE
Trans. Inf. Theory, vol. 62, no. 4, pp. 1878 – 1896, Apr. 2016.
[19] C. Chan, A. Al-Bashabsheh, J. Ebrahimi, T. Kaced, and T. Liu, “Multivariate mutual information inspired by secret-key agreement,” Proc.
IEEE, vol. 103, no. 10, pp. 1883–1913, Oct. 2015.
[20] C. Chan, A. Al-Bashabsheh, J. B. Ebrahimi, T. Kaced, S. Kadhe, T. Liu,
A. Sprintson, M. Yan, and Q. Zhou, “Successive omniscience,” in Proc.
Int. Symp. Network Coding, Sydney, Australia, 2015, pp. 21–25.
[21] N. Milosavljevic, S. Pawar, M. Gastpar, and K. Ramchandran, “Efficient
algorithms for the data exchange problem under fairness constraints,” in
Proc. Annu. Allerton Conf. Commun., Control, and Comput., Monticello,
IL, 2012, pp. 502–508.

26

[22] N. Ding, R. A. Kennedy, and P. Sadeghi, “Fairest constant sum-rate
transmission for cooperative data exchange: An M -convex minimization
approach,” in Proc. 22nd Int. Conf. Telecommun., Sydney, Australia,
2015, pp. 36–42.
[23] ——, “Iterative merging algorithm for cooperative data exchange,” in
Proc. Int. Symp. Network Coding, Sydney, Australia, 2015, pp. 41–45.
[24] S. Fujishige, “Polymatroidal dependence structure of a set of random
variables,” Inf. Control, vol. 39, no. 1, pp. 55 – 72, Oct. 1978.
[25] J. Edmonds, “Submodular functions, matroids, and certain polyhedra,”
in Combinatorial Optimization—Eureka, You Shrink! Berlin, Germany:
Springer, 2003, pp. 11–26.
[26] S. Fujishige, Submodular functions and optimization, 2nd ed. Amsterdam, The Netherlands: Elsevier, 2005.
[27] C. Chan, “On tightness of mutual dependence upperbound for secret-key
capacity of multiple terminals,” arXiv preprint arXiv:0805.3200, 2008.
[28] P. Narayan and H. Tyagi, “Multiterminal secrecy by public discussion,”
Foundations and Trends in Communications and Information Theory,
vol. 13, no. 2-3, pp. 129–275, 2016.
[29] L. Lovász, “Submodular functions and convexity,” in Mathematical
Programming The State of the Art: Bonn 1982. Berlin, Germany:
Springer, 1983, pp. 235–257.
[30] R. W. Yeung, Information theory and network coding. Berlin, Germany:
Springer Science & Business Media, 2008.
[31] H. Narayanan, Submodular functions and electrical networks. Amsterdam, The Netherlands: Elsevier, 1997.
[32] R. P. Dilworth, “Dependence relations in a semi-modular lattice,” Duke
Math. J., vol. 11, no. 3, pp. 575–587, Feb. 1944.
[33] H. Narayanan, “The principal lattice of partitions of a submodular
function,” Linear Algebra its Appl., vol. 144, pp. 179 – 216, Jan. 1991.
[34] A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency.
Berlin: Springer-Verlag, 2003.
[35] M. Baı̈ou, F. Barahona, and A. R. Mahjoub, “Partition inequalities:
Separation, extensions and network design,” Prog. Comb. Optim, pp.
1–39, Nov. 2011.
[36] V. Kolmogorov, “A faster algorithm for computing the principal sequence of partitions of a graph,” Algorithmica, vol. 56, no. 4, pp. 394–
412, 2010.
[37] E. Cheng and W. H. Cunningham, “A faster algorithm for computing
the strength of a network,” Inf. Process. Lett., vol. 49, no. 4, pp. 209 –
212, Feb. 1994.
[38] L. Khachiyan, “Polynomial algorithms in linear programming,” USSR
Comput. Math. Math. Physics, vol. 20, no. 1, pp. 53 – 72, 1980.
[39] M. Grötschel, L. Lovász, and A. Schrijver, Geometric algorithms and
combinatorial optimization.
Berlin, Germany: Springer Science &
Business Media, 2012.
[40] ——, “The ellipsoid method and its consequences in combinatorial
optimization,” Combinatorica, vol. 1, no. 2, pp. 169–197, Jun. 1981.
[41] S. Iwata, “Submodular function minimization,” Math. Programming, vol.
112, no. 1, pp. 45–64, Mar. 2007.
[42] S. Iwata, L. Fleischer, and S. Fujishige, “A combinatorial strongly
polynomial algorithm for minimizing submodular functions,” J. ACM,
vol. 48, no. 4, pp. 761–777, Jul. 2001.
[43] S. Fujishige and S. Isotani, “A submodular function minimization
algorithm based on the minimum-norm base,” Pacific J. Optimization,
vol. 7, no. 1, pp. 3–17, 2011.
[44] J. B. Orlin, “A faster strongly polynomial time algorithm for submodular
function minimization,” Math. Programming, vol. 118, no. 2, pp. 237–
251, May 2009.
[45] N. Milosavljevic, S. Pawar, S. El Rouayheb, M. Gastpar, and K. Ramchandran, “Deterministic algorithm for the cooperative data exchange
problem,” in Proc. IEEE Int. Symp. Inf. Theory, St. Petersburg, Russia,
2011, pp. 410–414.
[46] K. Nagano, Y. Kawahara, and S. Iwata, “Minimum average cost clustering,” in Proc. Advances in Neural Inf. Process. Syst., Vancouver,
Candada, 2010, pp. 1759–1767.
[47] W. H. Cunningham, “Optimal attack and reinforcement of a network,”
J. ACM, vol. 32, no. 3, pp. 549–561, Jul. 1985.
[48] C. Chan, A. Al-Bashabsheh, Q. Zhou, T. Kaced, and T. Liu, “Infoclustering: A mathematical theory for data clustering,” arXiv preprint
arXiv:1605.01233, 2016.
[49] R. E. Bixby, W. H. Cunningham, and D. M. Topkis, “The partial order
of a polymatroid extreme point,” Math. Oper. Res., vol. 10, no. 3, pp.
367–378, 1985.
[50] S. Moriguchi, A. Shioura, and N. Tsuchimura, “M-convex function
minimization by continuous relaxation approach: Proximity theorem and
algorithm,” SIAM J. Optimization, vol. 21, no. 3, pp. 633–668, Jul. 2011.

IEEE TRANSACTIONS ON INFORMATION THEORY

[51] K. Nagano and K. Aihara, “Equivalence of convex minimization problems over base polytopes,” Japan J. Ind. Appl. Math., vol. 29, no. 3, pp.
519–534, 2012.
[52] T. Ibaraki and N. Katoh, Resource allocation problems: algorithmic
approaches. Cambridge, MA: MIT press, 1988.
[53] S. Moriguchi and A. Shioura, “On hochbaum’s proximity-scaling algorithm for the general resource allocation problem,” Math. Oper. Res.,
vol. 29, no. 2, pp. 394–397, May 2004.
[54] N. Ding, C. Chan, Q. Zhou, R. A. Kennedy, and P. Sadeghi, “Fairness in
communication for omniscience,” in Proc. IEEE Int. Symp. Inf. Theory,
Barcelona, 2016, pp. 2314–2318.
[55] S. Fujishige, “Lexicographically optimal base of a polymatroid with
respect to a weight vector,” Math. Oper. Res., vol. 5, no. 2, pp. 186–
196, May 1980.
[56] ——, “Structures of polyhedra determined by submodular functions on
crossing families,” Math. Programming, vol. 29, no. 2, pp. 125–141,
1984.
[57] K. Nagano and Y. Kawahara, “Structured convex optimization under
submodular constraints,” arXiv preprint arXiv:1309.6850, 2013.
[58] N. J. A. Harvey, D. R. Karger, and K. Murota, “Deterministic network
coding by matrix completion,” in Proc. Sixteenth Ann. ACM-SIAM Symp.
Discrete Algorithms, Philadelphia, PA, 2005, pp. 489–498.
[59] S. Fujishige, “Principal structures of submodular systems,” Discrete
Appl. Math., vol. 2, no. 1, pp. 77 – 79, 1980.

Ni Ding received the B.C.A. degree from the Shanghai Second Polytechnic
University, China, the B.E. degree in Telecommunications (1st class honours)
from the University of New South Wales, Australia, and the PhD degree
from the Australian National University, Australia, in 2005, 2012 and 2017,
respectively. From September 1998 to August 2006, she was an associate
engineer in Shanghai Telecom, China. She is now a postdoctoral fellow at
Data 61, The Commonwealth Scientific and Industrial Research Organisation
(CSIRO), Australia. Her research interests generally include optimizations in
information theory, wireless communications, signal processing and machine
learning. She is currently interested in the discrete and combinatorial optimization problems raised in discrete event control in cross-layer adaptive
modulation, source coding and network coding problems and game theory (in
particular, the games with strong structures, e.g., supermodular and convex
games).

Chung Chan received his B.Sc., M.Eng. and Ph.D. from the Electrical
Engineering and Computer Science Department at the Massachusetts Institute
of Technology (MIT) in 2004, 2005 and 2010 respectively. He is currently a
Research Assistant Professor at the Institute of Network Coding, the Chinese
University of Hong Kong, and the secretary of the IEEE Information Theory
Society Hong Kong Chapter. He will join the Department of Computer
Science, City University of Hong Kong, as an Assistant Professor in 2018. His
research interest is to develop general information measures and flow models
from network information theory that are applicable to practical problems in
machine learning. His research topics include the development of network
link models using matroids, the derivation of theoretical limits and optimal
strategies for the problems of multiterminal source coding, data exchange,
and secret generation. His most significant contribution is the extension of
Shannons mutual information to the multivariate case, and the discovery of its
connections to various problems in information theory and machine learning.

Qiaoqiao Zhou received his B.B.A. in business administration and M.S. in
electrical engineering from Beijing University of Post and Telecommunication,
China, in 2011 and 2014, respectively. In 2014-2015 he was a research assistant at Institute of Network Coding, the Chinese University of Hong Kong.
He is currently a Ph.D. student at Department of Information Engineering, the
Chinese University of Hong Kong. His research interests include informationtheoretic security and machine learning.

DING et al.: DETERMINING OPTIMAL RATES FOR COMMUNICATION FOR OMNISCIENCE

Rodney A. Kennedy received the B.E. degree (1st class honours and
university medal) from the University of New South Wales, Sydney, Australia,
the M.E. degree from the University of Newcastle, and the Ph.D. degree
from the Australian National University, Canberra. Since 2000 he has been
a Professor in engineering at the Australian National University, Canberra,
Australia. He has co-authored over 350 refereed journal or conference papers
and a book Hilbert Space Methods in Signal Processing (Cambridge Univ.
Press, 2013). He has been a Chief Investigator in a number of Australian
Research Council Discovery and Linkage Projects. His research interests
include digital signal processing, digital and wireless communications, and
acoustical signal processing.

Parastoo Sadeghi is an Associate Professor at the Research School of
Engineering, Australian National University, Canberra, Australia. She received
the B.E. and M.E. degrees in electrical engineering from Sharif University of
Technology, Tehran, Iran, in 1995 and 1997, respectively, and the Ph.D. degree
in electrical engineering from the University of New South Wales, Sydney,
Australia, in 2006. From 1997 to 2002, she was a Research Engineer and
then a Senior Research Engineer at Iran Communication Industries, Tehran,
and at Deqx (formerly known as Clarity Eq), Sydney. She has visited various
research institutes, including the Institute for Communications Engineering,
Technical University of Munich, in 2008 and MIT in 2009 and 2013.
Dr. Sadeghi has co-authored around 140 refereed journal or conference
papers and a book on Hilbert Space Methods in Signal Processing (Cambridge
Univ. Press, 2013). She has been a Chief Investigator in a number of Australian
Research Council Discovery and Linkage Projects. Her research interests are
mainly in the areas of network coding, wireless communications systems,
and signal processing. Dr. Sadeghi was the recipient of two IEEE Region 10
Student Paper Awards for her research on the information theory of timevarying fading channels in 2003 and 2005.

27

