Abstract

This work considers the problem of distributed source coding of multiple sources
over a network with multiple receivers. Work by Ho et al. demonstrates that
random network coding can solve this problem at the high cost of jointly decod-
ing the source and the network code. Motivated by complexity considerations we
consider the problem of separating the source coding from the delivery of an ap-
propriate number of coded bits to each receiver. A multiplicative factor called the
“price of separation” is defined that measures the gap to separability for a partic-
ular network and source distribution. Both networks with capacities and networks
with costs on links are studied. We show that the problem with 2 sources and 2 re-
ceivers is always separable, and present counter-examples for other cases. Bounds
are presented on the “price of separation”. While examples can be constructed
where separation does not hold, our experimental results show that in most cases
separation holds implying that existing solutions to the classical Slepian-Wolf prob-
lem can be effectively used over a network as well.

‚Äč