<p>I'm not aware of a general rule to convert centralized bounds to the distributed setting. In the distributed setting, local computation is given for free but the difficulty lies in <em>breaking the symmetry</em> - a node needs to accumulate enough information about it's neighborhood to make a decision about being part of the output set, e.g. being in the MIS. (Taking this a step further, we can think of an $r$-round algorithm as a function mapping $r$-neighborhoods to a yes/no decision.)</p>

<p>For example, for certain $n$-node graphs with max degree $\Delta$ there is an $\Omega(\sqrt{\log n}+\log \Delta)$ lower bound [2] known on the number of distributed rounds, that holds for (the distributed version of) computing a constant approximation of a minimum vertex cover or of a minimum dominating set. </p>

<p>While the above problems are known to be NP-complete, the same lower bound also holds for problems for which there are polynomial time centralized algorithms like computing a maximal independent set or finding a maximal matching. </p>

<p>For most of these problems the lower bound is almost tight; there are distributed algorithms that run in polylogarithmic rounds (see [2] and references therein).</p>

<p>On the other hand, some NP complete problems even allow constant time solutions in the distributed setting! In [1] there's an $O(1)$ round distributed algorithm for $O(n^{1/2+\varepsilon} \chi)$-coloring, which itself is NP complete.</p>

<p>[1] Leonid Barenboim. On the Locality of Some NP-Complete Problems
<a href="http://arxiv.org/abs/1204.6675">http://arxiv.org/abs/1204.6675</a></p>

<p>[2] Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer. Local Computation: Lower and Upper Bounds.
<a href="http://arxiv.org/pdf/1204.6675v1.pdf">http://arxiv.org/pdf/1204.6675v1.pdf</a></p>

CC BY-SA 3.0
2013-05-20T18:07:16.110Z
2013-05-20T18:07:16.110Z
Peter
<p>If we know some lower bound of the solution of a problem in centralized setting, what can we say about the lower bound in a distributed setting?</p>

CC BY-SA 3.0
2013-05-20T19:42:10.083Z
It is highly dependent on precisely what you mean by a "distributed setting". What is your model of computation? In most cases the answer is trivial once you fix the model of computation: either we can simulate any distributed algorithm efficiently in a centralised setting (with, say, linear overhead), or we have explicitly given some extra power to the distributed algorithm that does not admit any centralised simulation (cf., the usual LOCAL model in which local computation is unbounded).
Jukka Suomela
<ds.algorithms><dc.distributed-comp>
bounds in centralized and distributed
user55531
# bounds in centralized and distributed

(Asked by: username_0 on 2013-05-20)

If we know some lower bound of the solution of a problem in centralized setting, what can we say about the lower bound in a distributed setting?

**Tags:** ds.algorithms, dc.distributed-comp
> **Comments:**
> **username_1**: It is highly dependent on precisely what you mean by a "distributed setting". What is your model of computation? In most cases the answer is trivial once you fix the model of computation: either we can simulate any distributed algorithm efficiently in a centralised setting (with, say, linear overhead), or we have explicitly given some extra power to the distributed algorithm that does not admit any centralised simulation (cf., the usual LOCAL model in which local computation is unbounded).  

---

## 1 answers

### Answer by username_2 on 2013-05-20. Score: 5

I'm not aware of a general rule to convert centralized bounds to the distributed setting. In the distributed setting, local computation is given for free but the difficulty lies in *breaking the symmetry* - a node needs to accumulate enough information about it's neighborhood to make a decision about being part of the output set, e.g. being in the MIS. (Taking this a step further, we can think of an $r$-round algorithm as a function mapping $r$-neighborhoods to a yes/no decision.)

For example, for certain $n$-node graphs with max degree $\Delta$ there is an $\Omega(\sqrt{\log n}+\log \Delta)$ lower bound [2] known on the number of distributed rounds, that holds for (the distributed version of) computing a constant approximation of a minimum vertex cover or of a minimum dominating set.

While the above problems are known to be NP-complete, the same lower bound also holds for problems for which there are polynomial time centralized algorithms like computing a maximal independent set or finding a maximal matching.

For most of these problems the lower bound is almost tight; there are distributed algorithms that run in polylogarithmic rounds (see [2] and references therein).

On the other hand, some NP complete problems even allow constant time solutions in the distributed setting! In [1] there's an $O(1)$ round distributed algorithm for $O(n^{1/2+\varepsilon} \chi)$-coloring, which itself is NP complete.

[1] Leonid Barenboim. On the Locality of Some NP-Complete Problems
<http://arxiv.org/abs/1204.6675>

[2] Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer. Local Computation: Lower and Upper Bounds.
<http://arxiv.org/pdf/1204.6675v1.pdf>


---

