[IEEE Trans. on Information Theory, February 2011, pp. 1015-1030]
Network Coding for Computing: Cut-Set Bounds
Rathinakumar Appuswamy, Massimo Franceschetti, Nikhil Karamchandani, and Kenneth Zeger
Abstract
The following 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 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 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 differnet 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.