Time and Energy Complexity of Function Computation Over Networks

Abstract

This paper considers the following network computation problem: <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> nodes are placed on a √n × √n grid, each node is connected to every other node within distance <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">r</i> ( <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> ) of itself, and it is assigned an arbitrary input bit. Nodes communicate with their neighbors and a designated sink node computes a function <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">f</i> of the input bits, where <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">f</i> is either the identity or a symmetric function. We first consider a model where links are interference and noise-free, suitable for modeling wired networks. Then, we consider a model suitable for wireless networks. Due to interference, only nodes which do not share neighbors are allowed to transmit simultaneously, and when a node transmits a bit, all of its neighbors receive an independent noisy copy of the bit. We present lower bounds on the minimum number of transmissions and on the minimum number of time slots required to compute <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">f</i> . We also describe efficient schemes that match both of these lower bounds up to a constant factor and are thus jointly (near) optimal with respect to the number of transmissions and the number of time slots required for computation. At the end of the paper, we extend results on symmetric functions to general network topologies, and obtain a corollary that answers an open question posed by El Gamal in 1987 regarding the computation of the parity function over ring and tree networks.