Efficient Flow Allocation Algorithms for In-Network Function Computation
Authors:
- Virag ShahVSVirag Shah
- Bikash Kumar DeyBDBikash Kumar Dey
- D. ManjunathDMD. Manjunath
- 1 December 2011
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-6
Abstract
We consider in-network computation of an arbitrary function over an arbitrary communication network. We consider the same model as our earlier work in [1]. The given network consists of directed/undirected links with capacity constraints, some source nodes which generate data, and other intermediate forwarding nodes. An arbitrary function of this distributed data is to be computed at a terminal node. The structure of the function is described by a given computation schema represented by a directed tree. In our earlier work, we presented a linear program to define the maximum rate of computation, and then introduced a notion of flow-conservation suitable in this context so as to come up with a flow-conservation based linear program which can be solved in polynomial time. In this paper, we develop a combinatorial primal-dual algorithm to obtain (1-∈)-approximate solutions to these linear programs. As a part of this, we present an algorithm to find a minimum-cost embedding in a network of weighted links--which is of independent interest. We then describe application of our techniques to other practically interesting problems of multiple terminals wanting different functions, computation with a given desired precision, and to networks with energy constraints at nodes.Keywords
This publication has 10 references indexed in Scilit:
- Network flows for functions2011
- Error-free multi-valued consensus with byzantine failures2011
- On distributed function computation in structure-free random networks2008
- Computing and communicating functions over sensor networksIEEE Journal on Selected Areas in Communications, 2005
- Faster and simpler algorithms for multicommodity flow and other fractional packing problems2002
- Coding for computingIEEE Transactions on Information Theory, 2001
- Speeding-up linear programming using fast matrix multiplication1989
- Finding parity in a simple broadcast networkIEEE Transactions on Information Theory, 1988
- A dichotomy of functionsF(X, Y)of correlated sources(X, Y)IEEE Transactions on Information Theory, 1987
- A new polynomial-time algorithm for linear programming1984