Communicating the Sum of Sources Over a Network
By Aditya Ramamoorthy, Michael Langberg. 2010
83 citations recorded by the source corpus.
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 X<sub>i</sub> wish to communicate the sum ΣX<sub>i</sub> to a set of terminals t<sub>j</sub>. 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 s<sub>i</sub>/t<sub>j</sub> is 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 ΣX<sub>i</sub>. We then present an efficient encoding scheme which enables the communication of ΣX<sub>i</sub> for the three sources, three terminals case, given that each source terminal pair is connected by two edge disjoint paths.
Subfields: Computer Networks and Communications, Electrical and Electronic Engineering
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computer Networks and Communications
- Amir Salman Avestimehr
- Qian Yu
- Mohammad Ali Maddah-Ali
- Songze Li
- Hariharan Rahul
- Omid Salehi-Abari
- Dina Katabi
- Jungwoo Lee
In Electrical and Electronic Engineering
- Hariharan Rahul
- Omid Salehi-Abari
- Dina Katabi
- Amir Salman Avestimehr
- Mohammad Ali Maddah-Ali
- Songze Li
- Syed Ali Jafar
- Kaibin Huang
Citations in the corpus
- Over-the-air Function Computation in Sensor Networks (2016, background): “ over the air. (c) Information Theoretical Approaches to Distributed Function Computation:Therehas beena lotof recentinterest in distributed function computation from the information theory community [10, 28, 3, 22, 11]. This work either does not take advantage of the properties of the wireless chan”
- A Fundamental Tradeoff Between Computation and Communication in Distributed Computing (2016, background): “Following these two seminal works, a wide range of communication problems in the scope of distributed computing have been studied (cf. [10]–[15]).”