[Information Theory and its Applications Workshop (ITA), San Diego, California, February 2011 (poster session)]
Network computing and linear codes
Rathinakumar Appuswamy, Massimo Franceschetti, Nikhil Karamchandani, and Kenneth Zeger
Abstract
We present a natural model of network computing that is closely related to the
network coding model of Ahlswede, Cai, Li, and Yeung and introduce the notions
of computing capacity and solvability for a given network and a target function.
Borrowing ideas from communication complexity and graph theory, we obtain an upper bound
on the computing capacity for arbitrary target functions and networks.
In addition, lower bounds on the computing capacity are given for several subclasses
of target functions.
We introduce the notion of linearly-reducible target functions and
show that linear network codes may provide a computing capacity advantage over routing only
when the receiver demands a linearly-reducible target function. Many known target
functions including the arithmetic sum, minimum, and maximum are not linearly-reducible.
Thus, the use of non-linear codes is essential in order to obtain a computing
capacity advantage over routing if the receiver demands a target function that
is not linearly-reducible.
We consider the scenario in which the source alphabet is a finite field and the target
function is linear and obtain an algebraic characterization to test whether an arbitrary network can compute
a linear target function using linear codes.
We identify a class of linear functions that can be computed using linear codes
in every network that satisfies a natural cut-based condition.
Conversely, for another class of linear functions, we show that the cut-based condition
does not guarantee the existence of a linear coding solution.