| Abstract |
A crucial part of distributed analytics is to average multiple weight vectors, each at a given node in a network, and to distribute this average to all nodes. For example, an algorithm for distributed gradient descent [1] uses this averaging operation and the convergence time of the algorithm depends on the time taken for averaging. In this paper, we propose an efficient algorithm for performing distributed averaging in a tactical networked system with bandwidth constraints. We make the following assumptions: 1) the size of the vectors is large; 2) there is no latency on the communication pipelines between nodes; 3) the bit length of the numbers is large compared to the logarithm of the size of the network; 4) the processing speed at the nodes is fast compared to the bandwidths of the communication pipelines; 5) the communication pipelines are unidirectional (but there may be two pipelines between two nodes, one in either direction). We analyse the problem from a theoretical perspective and present a 2-approximation algorithm to solve the problem. |