Worst-case asymmetric distributed function computation.
Saved in:
| Title: | Worst-case asymmetric distributed function computation. |
|---|---|
| Authors: | Agnihotri, Samar1 (AUTHOR) samar.agnihotri@gmail.com, Venkatachalapathy, Rajesh2 (AUTHOR) |
| Source: | International Journal of General Systems. Apr2013, Vol. 42 Issue 3, p268-293. 26p. 5 Diagrams, 2 Charts. |
| Subjects: | Wireless sensor networks, Mathematical functions software, Wireless communications, Telecommunication systems, Information resources, Set theory |
| Abstract: | We consider a distributed function computation problem where an information sink communicates withNcorrelated information sources to compute a given deterministic function of source data. A data-vectoris drawn from a discrete and finite probability distributionand componentxiis revealed toith,, source. We address this problem inasymmetric communicationscenarios where only the sink knows the distribution P. We are interested in computing the minimum number of source bits required,in the worst-case, to solve this problem. We propose the notion offunctional ambiguityto carry out the worst-case information-theoretic analysis of distributed function computation problems. We establish its various characteristics and prove that it leads to a valid information measure. Then, we provide a constructive solution for the distributed function computation problem in terms of an interactive communication protocol and prove its optimality. Finally, we establish two equivalence classes ofcompressibleandincompressiblefunctions to classify the set of all computable multivariate functions based on the minimum number of source bits needed in the worst-case to compute a function in the distributed function computation set-up. [ABSTRACT FROM AUTHOR] |
| Copyright of International Journal of General Systems is the property of Taylor & Francis Ltd and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| Abstract: | We consider a distributed function computation problem where an information sink communicates withNcorrelated information sources to compute a given deterministic function of source data. A data-vectoris drawn from a discrete and finite probability distributionand componentxiis revealed toith,, source. We address this problem inasymmetric communicationscenarios where only the sink knows the distribution P. We are interested in computing the minimum number of source bits required,in the worst-case, to solve this problem. We propose the notion offunctional ambiguityto carry out the worst-case information-theoretic analysis of distributed function computation problems. We establish its various characteristics and prove that it leads to a valid information measure. Then, we provide a constructive solution for the distributed function computation problem in terms of an interactive communication protocol and prove its optimality. Finally, we establish two equivalence classes ofcompressibleandincompressiblefunctions to classify the set of all computable multivariate functions based on the minimum number of source bits needed in the worst-case to compute a function in the distributed function computation set-up. [ABSTRACT FROM AUTHOR] |
|---|---|
| ISSN: | 03081079 |
| DOI: | 10.1080/03081079.2012.708342 |
