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?

  • 1
    $\begingroup$ 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). $\endgroup$ May 20 '13 at 19:42

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.