# How do you compute the time complexity of distributed algorithms?

How to compute the run-time of distributed algorithms in message passing systems? I was reading across and found it very weird that any computation done in each node is considered to take $\mathcal{O}(1)$ time due to the unreliability in the time it takes to pass messages. Since this approach is not practical at all, I am assuming that I have not understood it properly. Could someone please explain?

By impractical, I mean that I can simply solve any NP-Hard problem in distributed computing trivially in $\mathcal{O}(n^2)$ time by passing information throughout the network and then brute-forcing for the solution in $\mathcal{O}(1)$ time and this obviously seems stupid since in real life message passing shouldn't take more time than a brute-force solution over the search space.

• Does it by any chance simplify the algorithm to tell only about the message passing algorithm (with bound $\Omega(n \log n)$ messages or $\mathcal O(n^{\frac{3}{2}}\log^2 n)$)? Otherwise, as you noted, two threads simulating nodes would do some heavy magic. – Evil May 1 '17 at 5:53

You understood it right. The standard models of distributed computing typically assume that local computation is free. It follows that in the LOCAL model of distributed computing, you can solve any graph problem in time $O(n)$, and in the CONGEST model of distributed computing, you can solve any graph problem in time $O(m)$ by brute force; here $n$ is the number of nodes and $m$ is the number of edges.

However, we are not interested in such running times in these models. For example, for the LOCAL model, the key question is what can be solved e.g. in polylogarithmic time time, or $O(\log n)$ time, or $O(\log^* n)$ time, or even $O(1)$ time. Now these are highly non-trivial questions even if you assume that local computation is free.

LOCAL and CONGEST are usually the wrong models if you are interested in studying e.g. NP-hard problems. However, if you consider "easy" problems (e.g. something that you can trivially solve in linear time with a centralised algorithm), then these models become much more interesting. Yes, of course you can find a maximal matching or a maximal independent set in linear time, but can you find it in sublinear time?

Here are the key definitions for reference:

• LOCAL model: running time = number of synchronous rounds until all nodes stop and announce their local outputs; in each round each node can send a message to each of its neighbours; the message size is unbounded; local computation is free.

• CONGEST model: as above, but messages are bounded to $O(\log n)$ bits.

• Do you know of any models of computation that are suitable for NP-hard problems in distributed computing? – Banach Tarski May 2 '17 at 11:09

Time complexity is always measured relative to some model. For example, the $\Theta(n \log n)$ bound on sorting is the number of comparisons performed. If comparisons are not constant time, then the total number of operations will be higher.

Because of the high variability, and the overall time taken, often distributed algorithms are measured in terms of the number of messages sent. So in your example, you'd only solve it in $O(n^2)$ time if you assume that there is no cost to sending messages. If you're sending each possibility to a node, a good model will incorporate that cost, and you won't get magically fast solutions to $NP$-hard problems.

Also, for parallel computing, you model (approximately) how many nodes you have. It's a safe-bet to assume that you don't have more than $O(\log n)$ nodes for an input of size $n$. You certainly won't be able to scale your nodes exponentially, so brute-forcing doesn't always work.

Often, the computation done in distributed algorithms is minimal, or the computational content itself is intense, but orthogonal to the distributed nature of the algorithm (i.e. the algorithm is written over some abstract, computationally intensive task). In these cases, you usually only care about the messages sent or some other cost metric, since you might never know how many steps your computation takes.

• Yes that makes a lot of sense. So are there models of distributed computing where can analyze the computation time complexity and message passing time complexity separately? – Banach Tarski May 1 '17 at 9:15