  We derive information-theoretic converses (i.e., lower bounds) for the
minimum time required by any algorithm for distributed function computation
over a network of point-to-point channels with finite capacity, where each node
of the network initially has a random observation and aims to compute a common
function of all observations to a given accuracy with a given confidence by
exchanging messages with its neighbors. We obtain the lower bounds on
computation time by examining the conditional mutual information between the
actual function value and its estimate at an arbitrary node, given the
observations in an arbitrary subset of nodes containing that node. The main
contributions include: 1) A lower bound on the conditional mutual information
via so-called small ball probabilities, which captures the dependence of the
computation time on the joint distribution of the observations at the nodes,
the structure of the function, and the accuracy requirement. For linear
functions, the small ball probability can be expressed by L\'evy concentration
functions of sums of independent random variables, for which tight estimates
are available that lead to strict improvements over existing lower bounds on
computation time. 2) An upper bound on the conditional mutual information via
strong data processing inequalities, which complements and strengthens existing
cutset-capacity upper bounds. 3) A multi-cutset analysis that quantifies the
loss (dissipation) of the information needed for computation as it flows across
a succession of cutsets in the network. This analysis is based on reducing a
general network to a line network with bidirectional links and self-links, and
the results highlight the dependence of the computation time on the diameter of
the network, a fundamental parameter that is missing from most of the existing
lower bounds on computation time.
