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?
How does communication complexity relate to time complexity in distributed algorithms?
time complexity;dc.distributed comp