Computer Science – Networking and Internet Architecture
Scientific paper
2010-09-30
Computer Science
Networking and Internet Architecture
16 pages, 4 figures
Scientific paper
We consider in-network computation of an arbitrary function over an arbitrary communication network. A network with capacity constraints on the links is given. Some nodes in the network generate data, e.g., like sensor nodes in a sensor network. An arbitrary function of this distributed data is to be obtained at a terminal node. The structure of the function is described by a given computation schema, which in turn is represented by a directed tree. We design computing and communicating schemes to obtain the function at the terminal at the maximum rate. For this, we formulate linear programs to determine network flows that maximize the computation rate. We then develop fast combinatorial primal-dual algorithm to obtain $\epsilon$-approximate solutions to these linear programs. We then briefly describe extensions of our techniques to the cases of multiple terminals wanting different functions, multiple computation schemas for a function, computation with a given desired precision, and to networks with energy constraints at nodes.
Dey Bikash Kumar
Manjunath D.
Shah Virag
No associations
LandOfFree
Network Flows for Functions 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 Flows for Functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network Flows for Functions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-242612