Inspired by this question, what are the major problems and existing solutions which needs improvement in (theoretical) distributed systems domain.
Something like membership protocols, data consistency?
$\begingroup$
$\endgroup$
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
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. 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 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 — 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.
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 that such lower bounds would also imply new lower bounds for ACC.
answered Apr 2, 2015 at 14:40
$\begingroup$
$\endgroup$
1
Open problems on "Distributed Algorithms for Minimum Spanning Trees (MST)": (listed in [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.
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.
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 by Sergio Rajsbaum in "Encyclopedia of Algorithms", 2008.
[2] Distributed MST for constant diameter graphs by Lotker et al. Distrib. Comput., 2006.
[3] Minimum weight spanning tree construction in $O(\log \log n)$ communication rounds by Lotker et al. SIAM J. Comput., 35(1), 2005.
[4] A Fast Distributed Approximation Algorithm for Minimum Spanning Trees by Khan et al. DISC 2006.
-
3$\begingroup$ Regarding the 3rd item: an upper bound of $O(\log \log \log n)$ is also known, see 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). $\endgroup$ Apr 5, 2015 at 10:42
$\begingroup$
$\endgroup$
see also (more recently) a slideshow "Unsolved Computer Science Problems in Distributed Computing" from 2012 by Notre Dame researcher Douglas Thain 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?
