1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ It's the same as a sum, which depends on the network topology. $\endgroup$ Oct 6 '15 at 20:01
  • $\begingroup$ 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. $\endgroup$ Nov 16 '15 at 22:21
2
$\begingroup$

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.

How you do that efficiently will depend on the network topology and the communication protocol.

$\endgroup$
4
  • $\begingroup$ Right, my question is what the best known way to do that is. $\endgroup$
    – elplatt
    Oct 7 '15 at 14:45
  • 1
    $\begingroup$ That's unanswerable as it stands. As I said, that will depend on the network topology and the communication protocol. How are the nodes connected? As a mesh, a hypercube, a butterfly? Can you do concurrent reads/exclusive writes? All these parameters make a significant difference. $\endgroup$ Oct 7 '15 at 16:37
  • $\begingroup$ Whichever topology gives the best communication complexity. $\endgroup$
    – elplatt
    Oct 7 '15 at 20:23
  • $\begingroup$ I meant that it's the same as the sum because (assuming you avoid overflow) it IS the sum, followed by a division. I'm pretty sure an average of averages over ANY partition is not necessarily an average. Do you have a proof of that? $\endgroup$ Nov 8 '15 at 4:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.