Information-Theoretic Bounds for Multiround Function Computation in Collocated Networks
arXiv:0901.2356 · doi:10.1109/ISIT.2009.5205926
Abstract
We study the limits of communication efficiency for function computation in collocated networks within the framework of multi-terminal block source coding theory. With the goal of computing a desired function of sources at a sink, nodes interact with each other through a sequence of error-free, network-wide broadcasts of finite-rate messages. For any function of independent sources, we derive a computable characterization of the set of all feasible message coding rates - the rate region - in terms of single-letter information measures. We show that when computing symmetric functions of binary sources, the sink will inevitably learn certain additional information which is not demanded in computing the function. This conceptual understanding leads to new improved bounds for the minimum sum-rate. The new bounds are shown to be orderwise better than those based on cut-sets as the network scales. The scaling law of the minimum sum-rate is explored for different classes of symmetric functions and source parameters.
9 pages. A 5-page version without appendices was submitted to IEEE International Symposium on Information Theory (ISIT), 2009. This version contains complete proofs as appendices
References in corpus (1)
Cited by in corpus (13)
- Network Coding for Computing: Cut-Set Bounds
- Fundamentals of Large Sensor Networks: Connectivity, Capacity, Clocks and Computation
- Information-Theoretic Bounds for Multiround Function Computation in Collocated Networks
- Distributed Function Computation with Confidentiality
- On Computing a Function of Correlated Sources
- Optimal ordering of transmissions for computing Boolean threhold functions
- When is a Function Securely Computable?
- Towards a Queueing-Based Framework for In-Network Function Computation
- Computing linear functions by linear coding over networks
- Optimal computation of symmetric Boolean functions in Tree networks
- Optimal strategies for computing symmetric Boolean functions in collocated networks
- Infinite-message Interactive Function Computation in Collocated Networks
- Optimal Function Computation in Directed and Undirected Graphs