# How does communication complexity relate to time complexity in distributed algorithms?

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?

• 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. – Jukka Suomela Jun 15 '17 at 21:10
• 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? – lamba Jun 15 '17 at 21:46
• 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. – Jukka Suomela Jun 15 '17 at 22:28
• Thanks, I'll think about that one. Do you now of any good references (or textbooks) that describes the typical distributed computing model? – lamba Jun 16 '17 at 8:55