Multi-Function Computation over a Directed Acyclic Network

The problem of multi-function computation over a directed acyclic network is investigated in this paper. In such a network, a sink node is required to compute with zero error multiple vector-linear functions, where each vector-linear function has distinct inputs generated by multiple source nodes. The <i>computing rate tuple</i> of an admissible code is defined as a tuple consisting of the average number of zero-error computations for each vector-linear function when the network is used once jointly. From the information theoretic point of view, we are interested in characterizing the <i>rate region</i>, which is defined as the closed set of all achievable computing rate tuples. In particular, when the sink node is required to compute a single vector-linear function, the <i>network multi-function computation</i> problem degenerates to the <i>network function computation</i> problem. We prove an outer bound on the rate region by developing the approach of the cut-set strong partition. We also illustrate that the obtained outer bound is tight for a typical model of computing two vector-linear functions over the diamond network. Furthermore, we establish the relationship between the network multi-function computation rate region and the network function computation rate region. Also, we show that the best known outer bound on the rate region for computing an arbitrary vector-linear function over an arbitrary network is a straightforward consequence of our outer bound.