# Complexity of calculating average across distributed network?

What is the communication complexity of the best known algorithm for computing the average of a set of N*D numbers distributed across N nodes with D values per node? Assume you have full control over the network topology and protocol.

• It's the same as a sum, which depends on the network topology. Oct 6 '15 at 20:01
• If all you care about is communication, D>1 is equivalent to D=1. N-1 partial sums must be sent regardless of topology. You can rearrange the network to minimize time or diameter or degree, but you'll always need at least N-1 transmissions. Every receiver can incorporate what it receives into its transmissions, so you'll never need more than N-1 transmissions. WRT communication complexity, all reduction trees are equivalent. I'm not sure what kind of answer you want. Nov 16 '15 at 22:21

You could rely on the fact that, as @polygeric alluded to, the average of a set of numbers is the average of the averages over any partition of the original numbers. In other words, have each node compute the average of its $D$ numbers, send those $N$ averages somewhere and compute their averages.