Network Coding for Computing: Cut-Set Bounds

Details Network Coding for Computing: Cut-Set Bounds Network Coding for Computing: Cut-Set Bounds

2009-12-15

arxiv.org/abs/0912.2820v3

Computer Science

Information Theory

Submitted to the IEEE Transactions on Information Theory (Special Issue on Facets of Coding Theory: from Algorithms to Network

Scientific paper

The following \textit{network computing} problem is considered. Source nodes in a directed acyclic network generate independent messages and a single receiver node computes a target function $f$ of the messages. The objective is to maximize the average number of times $f$ can be computed per network usage, i.e., the ``computing capacity''. The \textit{network coding} problem for a single-receiver network is a special case of the network computing problem in which all of the source messages must be reproduced at the receiver. For network coding with a single receiver, routing is known to achieve the capacity by achieving the network \textit{min-cut} upper bound. We extend the definition of min-cut to the network computing problem and show that the min-cut is still an upper bound on the maximum achievable rate and is tight for computing (using coding) any target function in multi-edge tree networks and for computing linear target functions in any network. We also study the bound's tightness for different classes of target functions. In particular, we give a lower bound on the computing capacity in terms of the Steiner tree packing number and a different bound for symmetric functions. We also show that for certain networks and target functions, the computing capacity can be less than an arbitrarily small fraction of the min-cut bound.

Affiliated with

Also associated with

No associations

Rating

Network Coding for Computing: Cut-Set Bounds does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Network Coding for Computing: Cut-Set Bounds, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network Coding for Computing: Cut-Set Bounds will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-305034