Worst-case asymmetric distributed function computation

DOI10.1080/03081079.2012.708342MaRDI QIDQ5326145zbMATH OpenOpenAlexFDO

Authors Samar Agnihotri, Rajesh Venkatachalapathy

Publication date 31 July 2013

Published in International Journal of General Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.0207

zbMATH Keywords

wireless sensor networksinformation measuresinteractive communicationneural information processing systemsasymmetric communication scenariosdistributed function computationworst-case information-theoretic analysis

Mathematics Subject Classification ID

Decentralized systems (93A14) Stochastic systems in control theory (general) (93E03)

Abstract: We consider a worst-case asymmetric distributed source coding problem where an information sink communicates with $N$ correlated information sources to gather their data. A data-vector $$ is derived from a discrete and finite joint probability distribution $mathcalP=p(x_1,\mathrm{...},x_N)$ and component $x_i$ is revealed to the $i^{extrmth}$ source, $1leileN$. We consider an asymmetric communication scenario where only the sink is assumed to know distribution $mathcalP$. We are interested in computing the minimum number of bits that the sources must send, in the worst-case, to enable the sink to losslessly learn any $$ revealed to the sources. We propose a novel information measure called information ambiguity to perform the worst-case information-theoretic analysis and prove its various properties. Then, we provide interactive communication protocols to solve the above problem in two different communication scenarios. We also investigate the role of block-coding in the worst-case analysis of distributed compression problem and prove that it offers almost no compression advantage compared to the scenarios where this problem is addressed, as in this paper, with only a single instance of data-vector.

Recommendations

• scientific article; zbMATH DE number 5972643
• Distributed Symmetric Function Computation in Noisy Wireless Sensor Networks
• Protocols for asymmetric communication channels
• Three messages are not optimal in worst case interactive communication
• How to compress asymmetric communication

Cites work

• scientific article; zbMATH DE number 42862 (Why is no real title available?)
• scientific article; zbMATH DE number 1168332 (Why is no real title available?)
• A dichotomy of functions<tex>F(X, Y)</tex>of correlated sources<tex>(X, Y)</tex>
• Channel Coding Rate in the Finite Blocklength Regime
• Coding for computing
• Coding for interactive communication
• Communication Complexity
• Elements of Information Theory
• Finding parity in a simple broadcast network
• How to encode the modulo-two sum of binary sources (Corresp.)
• Noiseless coding of correlated information sources
• Rhythms of the brain.
• Some Results on Distributed Source Coding for Interactive Function Computation
• Uncertainty and information: foundations of generalized information theory.
• Worst-case interactive communication. I. Two messages are almost optimal

This page was built for publication: Worst-case asymmetric distributed function computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5326145)