<p>The <strong>distributed time complexity</strong> of numerous <strong>graph problems</strong> is still an open question.</p>

<p>In general, distributed graph algorithms is an area in which we would expect to have (at least asymptotically) <strong>matching upper and lower bounds</strong> for the distributed time complexity of graph problems. For example, for many optimisation problems <a href="http://arxiv.org/abs/1011.5470">tight bounds are known</a>. However, there are lots of classical symmetry-breaking problems that are still poorly understood.</p>

<p>We do not know, for example, how many communication rounds does it take to find a <strong>maximal independent set</strong>, a <strong>maximal matching</strong>, a proper <strong>vertex colouring</strong> with $\Delta+1$ colours, or a proper <strong>edges colouring</strong> with $2\Delta-1$ colours in a graph with a maximum degree of $\Delta$. All of these problems are easy to solve with greedy centralised algorithms, and there are efficient distributed algorithms for each of these problems, but we do not know if any of the current algorithms are optimal.</p>

<p>For example, for all of these problems there are deterministic distributed algorithms for the LOCAL model with running times of $O(\Delta + \log^* n)$, where $n$ is the number of nodes. It is <a href="http://dx.doi.org/10.1137/0221015">well known</a> that these problems cannot be solved in time $O(\Delta) + o(\log^* n)$ rounds, but it is not known if they can be solved in time $o(\Delta) + O(\log^* n)$ rounds. In general, we do not understand how the <a href="https://users.ics.aalto.fi/suomela/lbla/">running times depend on the maximum degree</a> — this is what I call the <strong>local coordination problem</strong>.</p>

<p>The role of <strong>randomness</strong> is another major issue. For example, many of the above-mentioned problems can be solved in polylog-time with randomised algorithms (i.e., the time is polylog in $n$ for any value of $\Delta$), but no polylog-time deterministic algorithms are known for e.g. maximal independent sets. This questions, as well as many other open problems, are discussed in more detail in Section 11 of the <a href="http://www.cs.bgu.ac.il/~elkinm/book.pdf">recent book by Barenboim and Elkin</a>.</p>

<hr>

<p>Above, I have focused on questions that are specific to distributed computing. There are also open questions in distributed graph algorithms that have nontrivial connections to open problems in theoretical computer science in general. For example, non-constant lower bounds for the <strong>congested clique</strong> model are a big open question in distributed computing; <a href="http://dx.doi.org/10.1145/2611462.2611493">it was recently discovered</a> that such lower bounds would also imply new lower bounds for ACC.</p>

CC BY-SA 3.0
2015-04-02T14:40:55.737Z
2015-04-02T14:48:49.837Z
2015-04-02T14:48:49.837Z
Jukka Suomela
<p>Open problems on <strong>"Distributed Algorithms for Minimum Spanning Trees (MST)":</strong> (listed in [1])</p>

<ol>
<li><p>Concerning <em>time</em> complexity,</p>

<blockquote>
  <p>Near time optimal algorithms and lower bounds appear in [2] and references herein. The optimal time complexity remains an open problem.</p>
</blockquote></li>
<li><p>Concerning <em>message</em> complexity,</p>

<blockquote>
  <p>As far as <em>message complexity</em>, although the asymptotically tight bound of $O(m + n \log n)$ for the MST problem in general graphs is known, finding the actual constants remains an open problem.</p>
</blockquote></li>
<li><p>Concerning <em>synchronous</em> model:</p>

<blockquote>
  <p>In a synchronous model for overlay networks, where all processors are directly connected to each other, an MST can be constructed in sublogarithmic time, namely $O(\log \log n)$ communication rounds [3], and no corresponding lower bound is known.</p>
</blockquote></li>
</ol>

<p>Also note that there is an $O(\log n)$ <em>approximation</em> algorithm for distributed MST [4].</p>

<hr>

<p>[1] <a href="http://link.springer.com/referenceworkentry/10.1007%2F978-0-387-30162-4_116">Distributed Algorithms for Minimum Spanning Trees</a> by Sergio Rajsbaum in "Encyclopedia of Algorithms", 2008.</p>

<p>[2] <a href="https://www.eng.tau.ac.il/~boaz/cd/journal5.pdf">Distributed MST for constant diameter graphs</a> by Lotker et al. Distrib. Comput., 2006.</p>

<p>[3] <a href="http://epubs.siam.org/doi/abs/10.1137/S0097539704441848">Minimum weight spanning tree construction in $O(\log \log n)$ communication
rounds</a> by Lotker et al. SIAM J. 
Comput., 35(1), 2005.</p>

<p>[4] <a href="http://link.springer.com/chapter/10.1007%2F11864219_25">A Fast Distributed Approximation Algorithm for Minimum Spanning Trees</a> by Khan et al. DISC 2006.</p>

CC BY-SA 3.0
2015-04-05T10:42:05.633Z
Regarding the 3rd item: an upper bound of $O(\log \log \log n)$ is also known, see http://arxiv.org/abs/1412.2333 — and as I briefly mentioned in my answer, we nowadays understand a bit better why there has been so little progress with lower bounds for the congested clique model (nontrivial lower bounds for the congested clique model would imply nontrivial circuit complexity lower bounds).
Jukka Suomela
CC BY-SA 3.0
2015-04-04T06:22:28.487Z
2015-04-04T06:22:28.487Z
hengxin
<p>see also (more recently) a <a href="http://www3.nd.edu/~dthain/talks/unsolved-grid12.pptx" rel="nofollow">slideshow</a> "Unsolved Computer Science Problems in Distributed Computing" from 2012 by Notre Dame researcher <a href="http://www3.nd.edu/~dthain/" rel="nofollow">Douglas Thain</a> who leads their cooperative computing lab. it has more of an applied slant but the key questions listed inevitably lead to theoretical areas.</p>

<ul>
<li><p>The Kiloscale Problem: Any workflow with sufficient concurrency should be able to run correctly on 1K cores the first time and every time with no sysadmin help.</p></li>
<li><p>The Halting Problem: Given a workflow running on one thousand nodes, make it stop and clean up all associated state with complete certainty.</p></li>
<li><p>The Dependency Problem:</p>

<p>(1) Given a program, figure out everything that it actually needs to run on a different machine. </p>

<p>(2) Given a process, figure out the (distributed) resources it actually uses while running.</p>

<p>(3) Extend 1 and 2 to an entire workflow.</p></li>
<li><p>The Right-Sizing Problem: Given a (structured) application and a given cluster, cloud, or grid, choose a resource allocation that achieves good performance at acceptable cost.</p></li>
<li><p>The Troubleshooting Problem: When a failure happens in the middle of a 100-layer software stack, how and when do you report/retry/ignore/suppress the error?</p></li>
<li><p>The Design Problem: How should applications be designed so that they are well suited for distributed computing?</p></li>
</ul>

CC BY-SA 3.0
2015-04-01T15:55:54.547Z
2015-04-01T15:55:54.547Z
vzn
<p>See, for instance, <a href="http://www.cs.yale.edu/homes/aspnes/papers/beatcs-column-2006.pdf">Eight open problems in distributed computing</a>.</p>

CC BY-SA 3.0
2012-02-03T05:08:16.193Z
amazing paper! There goes my weekend! :)
zengr
CC BY-SA 3.0
2012-02-02T17:22:30.280Z
2012-02-02T17:22:30.280Z
Massimo Cafaro
<p>Inspired by this <a href="https://cstheory.stackexchange.com/questions/174/major-unsolved-problems-in-theoretical-computer-science">question</a>, what are the major problems and existing solutions which needs improvement in (theoretical) distributed systems domain.</p>

<p>Something like membership protocols, data consistency?</p>

<big-list><dc.distributed-comp>
Major unsolved problems in distributed systems?
zengr
# Major unsolved problems in distributed systems?

(Asked by: username_0 on 2012-02-02)

Inspired by this [question](https://cstheory.stackexchange.com/questions/174/major-unsolved-problems-in-theoretical-computer-science), what are the major problems and existing solutions which needs improvement in (theoretical) distributed systems domain.

Something like membership protocols, data consistency?

**Tags:** big-list, dc.distributed-comp

---

## 4 answers

### Answer by username_4 on 2012-02-02. Score: 30 | Accepted answer

See, for instance, [Eight open problems in distributed computing](http://www.cs.yale.edu/homes/aspnes/papers/beatcs-column-2006.pdf).

> **Comments:**
> **username_0**: amazing paper! There goes my weekend! :)  

---

### Answer by username_1 on 2015-04-02. Score: 15

The **distributed time complexity** of numerous **graph problems** is still an open question.

In general, distributed graph algorithms is an area in which we would expect to have (at least asymptotically) **matching upper and lower bounds** for the distributed time complexity of graph problems. For example, for many optimisation problems [tight bounds are known](http://arxiv.org/abs/1011.5470). However, there are lots of classical symmetry-breaking problems that are still poorly understood.

We do not know, for example, how many communication rounds does it take to find a **maximal independent set**, a **maximal matching**, a proper **vertex colouring** with $\Delta+1$ colours, or a proper **edges colouring** with $2\Delta-1$ colours in a graph with a maximum degree of $\Delta$. All of these problems are easy to solve with greedy centralised algorithms, and there are efficient distributed algorithms for each of these problems, but we do not know if any of the current algorithms are optimal.

For example, for all of these problems there are deterministic distributed algorithms for the LOCAL model with running times of $O(\Delta + \log^\* n)$, where $n$ is the number of nodes. It is [well known](http://dx.doi.org/10.1137/0221015) that these problems cannot be solved in time $O(\Delta) + o(\log^\* n)$ rounds, but it is not known if they can be solved in time $o(\Delta) + O(\log^\* n)$ rounds. In general, we do not understand how the [running times depend on the maximum degree](https://users.ics.aalto.fi/suomela/lbla/) — this is what I call the **local coordination problem**.

The role of **randomness** is another major issue. For example, many of the above-mentioned problems can be solved in polylog-time with randomised algorithms (i.e., the time is polylog in $n$ for any value of $\Delta$), but no polylog-time deterministic algorithms are known for e.g. maximal independent sets. This questions, as well as many other open problems, are discussed in more detail in Section 11 of the [recent book by Barenboim and Elkin](http://www.cs.bgu.ac.il/~elkinm/book.pdf).

---

Above, I have focused on questions that are specific to distributed computing. There are also open questions in distributed graph algorithms that have nontrivial connections to open problems in theoretical computer science in general. For example, non-constant lower bounds for the **congested clique** model are a big open question in distributed computing; [it was recently discovered](http://dx.doi.org/10.1145/2611462.2611493) that such lower bounds would also imply new lower bounds for ACC.


---

### Answer by username_2 on 2015-04-04. Score: 7

Open problems on **"Distributed Algorithms for Minimum Spanning Trees (MST)":** (listed in [1])

1. Concerning *time* complexity,

   > Near time optimal algorithms and lower bounds appear in [2] and references herein. The optimal time complexity remains an open problem.
2. Concerning *message* complexity,

   > As far as *message complexity*, although the asymptotically tight bound of $O(m + n \log n)$ for the MST problem in general graphs is known, finding the actual constants remains an open problem.
3. Concerning *synchronous* model:

   > In a synchronous model for overlay networks, where all processors are directly connected to each other, an MST can be constructed in sublogarithmic time, namely $O(\log \log n)$ communication rounds [3], and no corresponding lower bound is known.

Also note that there is an $O(\log n)$ *approximation* algorithm for distributed MST [4].

---

[1] [Distributed Algorithms for Minimum Spanning Trees](http://link.springer.com/referenceworkentry/10.1007%2F978-0-387-30162-4_116) by Sergio Rajsbaum in "Encyclopedia of Algorithms", 2008.

[2] [Distributed MST for constant diameter graphs](https://www.eng.tau.ac.il/~boaz/cd/journal5.pdf) by Lotker et al. Distrib. Comput., 2006.

[3] [Minimum weight spanning tree construction in $O(\log \log n)$ communication
rounds](http://epubs.siam.org/doi/abs/10.1137/S0097539704441848) by Lotker et al. SIAM J.
Comput., 35(1), 2005.

[4] [A Fast Distributed Approximation Algorithm for Minimum Spanning Trees](http://link.springer.com/chapter/10.1007%2F11864219_25) by Khan et al. DISC 2006.

> **Comments:**
> **username_1**: Regarding the 3rd item: an upper bound of $O(\log \log \log n)$ is also known, see http://arxiv.org/abs/1412.2333 — and as I briefly mentioned in my answer, we nowadays understand a bit better why there has been so little progress with lower bounds for the congested clique model (nontrivial lower bounds for the congested clique model would imply nontrivial circuit complexity lower bounds).  

---

### Answer by username_3 on 2015-04-01. Score: 4

see also (more recently) a [slideshow](http://www3.nd.edu/~dthain/talks/unsolved-grid12.pptx) "Unsolved Computer Science Problems in Distributed Computing" from 2012 by Notre Dame researcher [Douglas Thain](http://www3.nd.edu/~dthain/) who leads their cooperative computing lab. it has more of an applied slant but the key questions listed inevitably lead to theoretical areas.

* The Kiloscale Problem: Any workflow with sufficient concurrency should be able to run correctly on 1K cores the first time and every time with no sysadmin help.
* The Halting Problem: Given a workflow running on one thousand nodes, make it stop and clean up all associated state with complete certainty.
* The Dependency Problem:

  (1) Given a program, figure out everything that it actually needs to run on a different machine.

  (2) Given a process, figure out the (distributed) resources it actually uses while running.

  (3) Extend 1 and 2 to an entire workflow.
* The Right-Sizing Problem: Given a (structured) application and a given cluster, cloud, or grid, choose a resource allocation that achieves good performance at acceptable cost.
* The Troubleshooting Problem: When a failure happens in the middle of a 100-layer software stack, how and when do you report/retry/ignore/suppress the error?
* The Design Problem: How should applications be designed so that they are well suited for distributed computing?


---

