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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.