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 computing rate tuple 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 rate region, 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 network multi-function computation problem degenerates to the network function computation 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.