Some distributed algorithms (e.g. Bracha broadcast) runs in a constant number of rounds. I'm interested on how you'd analyse the time complexity of such algorithm, especially when the message size changes.

Let the message be $m$. If the communication complexity is $O(n^2 |m|)$, then for every node it's $O(n |m|)$. Assuming every unit of communication has some fixed computational overhead (e.g. receiving/sending/parsing). Can I argue that the time complexity is also $O(n |m|)$? What would be the formal way to do this?

  • 1
    $\begingroup$ It is easy to design a distributed algorithm that sends in total $\Theta(n)$ messages in $\Theta(n)$ rounds, and a distributed algorithm that sends in total $\Theta(n)$ messages in $\Theta(1)$ rounds. So the total number of messages or the total size of the messages is not related to the running time. $\endgroup$ – Jukka Suomela Jun 15 '17 at 21:10
  • $\begingroup$ I'm thinking more in terms of the number of operations rather than the number of round as time complexity. Suppose an algorithm runs in a constant number of rounds and $n$ is also a constant. Then I would imagine the time complexity would depend on the message size since the time required to process each message is non-negligible. Is this a reasonable assumption? $\endgroup$ – lamba Jun 15 '17 at 21:46
  • $\begingroup$ It seems that you have got some unusual model of distributed computing in mind. You will need to define the model of computing carefully first. $\endgroup$ – Jukka Suomela Jun 15 '17 at 22:28
  • $\begingroup$ Thanks, I'll think about that one. Do you now of any good references (or textbooks) that describes the typical distributed computing model? $\endgroup$ – lamba Jun 16 '17 at 8:55

Your Answer

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

Browse other questions tagged or ask your own question.