Distributed Function Computation Over a Rooted Directed Tree

This paper establishes the capacity region for a class of source coding function computation setups, where sources of information are available at the nodes of a tree and where a function of these sources must be computed at its root. The capacity region holds for any function as long as the sources...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2016-12, Vol.62 (12), p.7135-7152
Main Authors: Sefidgaran, Milad, Tchamkerten, Aslan
Format: Article
Language:English
Subjects:
Codes
Communication
Complexity theory
Distributed Computing
Entropy
Information theory
Markov analysis
Receivers
Source coding
Telecommunications
Transmitters
Tree Graphs
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper establishes the capacity region for a class of source coding function computation setups, where sources of information are available at the nodes of a tree and where a function of these sources must be computed at its root. The capacity region holds for any function as long as the sources' joint distribution satisfies a certain Markov criterion. This criterion is met, in particular, when the sources are independent. This result recovers the capacity regions of several function computation setups. These include the point-to-point communication setting with arbitrary sources, the noiseless multiple access network with conditionally independent sources, and the cascade network with Markovian sources.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2016.2530398