Communicating the sum of sources in a 3-sources/3-terminals network; revisited
Michael L. Langberg, Aditya Ramamoorthy · 2010
We consider the problem of multicasting sums over directed acyclic networks with unit capacity edges. A set of source nodes siobserve independent unit-entropy source processes Xiand want to communicate Σ Xito a set of terminals tj. Previous work on this problem has established necessary and sufficient conditions on the si-tjconnectivity in the case when there are two sources or two terminals (Ramamoorthy '08), and in the case of three sources and three terminals (Langberg-Ramamoorthy '09). In particular the latter result establishes that each terminal can recover the sum if there are two edge disjoint paths between each si-tjpair. In this work, we provide a new and significantly simpler proof of this result, and introduce techniques that may be of independent interest in other network coding problems.