Communicating the Sum of Sources Over a Network
Aditya Ramamoorthy, Michael L. Langberg · IEEE Journal on Selected Areas in Communications · 2013
We consider the network communication scenario, over directed acyclic networks with unit capacity edges in which a number of sources si each holding independent unit-entropy information Xiwish to communicate the sum ΣXito a set of terminals tj. We show that in the case in which there are only two sources or only two terminals, communication is possible if and only if each source terminal pair si/tjis connected by at least a single path. For the more general communication problem in which there are three sources and three terminals, we prove that a single path connecting the source terminal pairs does not suffice to communicate ΣXi. We then present an efficient encoding scheme which enables the communication of ΣXifor the three sources, three terminals case, given that each source terminal pair is connected by two edge disjoint paths.