Network flows for functions
Virag Shah, Bikash Kumar Dey, Deepika Revankar Manjunath · 2011
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., 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 define a new notion of conservation of flow suitable in this setup and 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. Our approach introduces the network flow techniques to the distributed function computation setup where such a scope was hitherto unsuspected due to the lack of traditional conservation of flow.