<p>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.</p>

<p>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?</p>

CC BY-SA 3.0
2017-06-15T21:10:36.643Z
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
CC BY-SA 3.0
2017-06-15T21:46:38.343Z
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
CC BY-SA 3.0
2017-06-15T22:28:22.767Z
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
CC BY-SA 3.0
2017-06-16T08:55:05.447Z
Thanks, I'll think about that one. Do you now of any good references (or textbooks) that describes the typical distributed computing model?
lamba
<time-complexity><dc.distributed-comp>
How does communication complexity relate to time complexity in distributed algorithms?
lamba
# How does communication complexity relate to time complexity in distributed algorithms?

(Asked by: username_0 on 2017-06-14)

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?

**Tags:** time-complexity, dc.distributed-comp
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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?  
> **username_1**: 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.  
> **username_0**: Thanks, I'll think about that one. Do you now of any good references (or textbooks) that describes the typical distributed computing model?  

---

## 0 answers

