<blockquote>
  <p>Is there a set of canonical distributed systems problems from which all the possible distributed system problems can be reduced to?</p>
</blockquote>

<p>I'm unaware of such a published list of problems. </p>

<p>Keep in mind that there are <em>many</em> different (and somewhat incomparable) models in distributed computing, ranging from the "benign" synchronous (fault-free) model where nodes execute in lock-step rounds and all messages are delivered 
reliably in each round, to the asynchronous model where there are no bounds on 
processing speeds and message delays and nodes themselves might crash or send 
corrupted messages. 
To further add to this variety, there are other requirements and assumptions 
that are orthogonal to synchrony and faults: the initial knowledge of nodes 
(network size, diameter of the network, maximum node degree, etc.), the ability 
to query a failure detectors, whether nodes have unique identifiers, atomicity 
of send &amp; receive steps, the maximum size of a single message, and many more.</p>

<p>The actual model at hand often implies a very different nature of 
question. (See [1] for more elaboration on these $2$ sub-communities in distributed computing.)
In models that are close to the fault-free synchronous model, researchers often 
look at the complexity of local computation, for example, <em>"What is the time and message 
complexity for computing a vertex coloring?"</em></p>

<p>When looking at failures on the other hand, the questions are more related to solvability issues like <em>"Is consensus solvable in this model?"</em> or <em>"Can we implement this fancy 
failure detector under these assumptions?"</em> </p>

<blockquote>
  <p>If there is not a canonical list what is the current list of problems and what reductions exist?</p>
</blockquote>

<p>There are many examples of such reductions in certain distributed computing 
models, I'll limit my answer to the following 2:</p>

<h2>Local computation in the (fault-free) synchronous model</h2>

<p>[2] show reductions between many optimization problems, for example, Minimum Dominating 
Set, Maximal Independent Set (MIS), Maximal Matching (MM), and Minimum Vertex 
Cover (MVC): In particular, [2] show a lower bound of $\Omega(\sqrt{\log n} + 
\log\Delta)$, where $n$ is the network size and $\Delta$ the max degree, for 
computing a constant approximation of an MVC. From this, the same bound follows 
for computing an MM, since any maximal matching is also a $2$-approximation of 
an MVC. From this, you also get a bound on computing an MIS, because an 
MIS-algorithm $A$ can be used to compute MM by simulating the execution of $A$ 
on the line graph. </p>

<h2>Asynchronous Model with Crash Failures</h2>

<p>Here the most studied problem is 
fault-tolerant consensus and its many variations, since implementing basic primitives like atomic broadcast and or a synchronizer themselves require consensus.</p>

<p>For example, assuming access to failure detectors [3], gives rise to a classification of problems by looking at 
the power of their respective failure detector.
We say that failure detector $S$ is the <em>weakest failure detector for problem</em> $P$, if, given any failure detector $T$ for $P$, you can also implement $S$.</p>

<p>Using this relation, we can define problem $P$ as being <em>harder</em> than problem $Q$, if 
the weakest failure detector for solving $P$ can implement the weakest failure 
detector for solving $Q$. 
It has recently been shown that <em>every</em> problem has a weakest failure detector [4]; note however, that [4] is an existential result. For some problems, e.g., consensus, the weakest failure detector is known [5], while for other problems, e.g., $k$-set agreement, the weakest falure detector is still open [6].</p>

<blockquote>
  <p>For example, I would say very naively that the leader election and mutual 
  exclusion problems can be reduced to the consensus problem. </p>
</blockquote>

<p>Sure, if you can solve consensus, you immediately have an algorithm for leader 
election: Simply use the ID of each node as the input for the consensus 
algorithm. The opposite way only holds in models where it is  guaranteed that the leader is eventually known to all. </p>

<p>[1] Pierre Fraigniaud: Distributed computational complexities: are you volvo-addicted or nascar-obsessed? PODC 2010.
<a href="http://doi.acm.org/10.1145/1835698.1835700">http://doi.acm.org/10.1145/1835698.1835700</a></p>

<p>[2] Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer: Local Computation: Lower and Upper Bounds. CoRR abs/1011.5470 (2010)
<a href="http://arxiv.org/abs/1011.5470">http://arxiv.org/abs/1011.5470</a></p>

<p>[3] Tushar Deepak Chandra, Sam Toueg: Unreliable Failure Detectors for Reliable Distributed Systems. J. ACM 43(2): 225-267 (1996).
<a href="http://doi.acm.org/10.1145/226643.226647">http://doi.acm.org/10.1145/226643.226647</a></p>

<p>[4] Prasad Jayanti, Sam Toueg: Every problem has a weakest failure detector. PODC 2008: 75-84.
<a href="http://doi.acm.org/10.1145/1400751.1400763">http://doi.acm.org/10.1145/1400751.1400763</a></p>

<p>[5] Tushar Deepak Chandra, Vassos Hadzilacos, Sam Toueg: The Weakest Failure Detector for Solving Consensus. J. ACM 43(4): 685-722 (1996)
<a href="http://doi.acm.org/10.1145/234533.234549">http://doi.acm.org/10.1145/234533.234549</a></p>

<p>[6] Michel Raynal: Failure Detectors to Solve Asynchronous k-Set Agreement: a Glimpse of Recent Results. Bulletin of the EATCS 103: 74-95 (2011)
<a href="http://albcom.lsi.upc.edu/ojs/index.php/beatcs/article/view/61">http://albcom.lsi.upc.edu/ojs/index.php/beatcs/article/view/61</a></p>

CC BY-SA 3.0
2013-04-04T04:04:17.037Z
Hagit Attiya and Faith Ellen have an upcoming book titled
"Impossibility Results for Distributed Computing".
Kaveh
CC BY-SA 3.0
2013-04-04T03:48:15.470Z
2013-04-04T03:48:15.470Z
Peter
<p>Last week, I was reading again Leslie's Lamport's 1982 trasncript of a conference he gave about <a href="http://research.microsoft.com/en-us/um/people/lamport/pubs/solved-and-unsolved.pdf">Solved Problems, Unsolved Problems and Non-Problems in Concurrency</a>. The paper is easily readable, but one of the things that got me thinking is the following assertion: </p>

<blockquote>
  <p>Can any problem be regarded as a mutual exclusion problem or a
  producer- consumer problem, or a combination of the two?</p>
</blockquote>

<p>I would like to know if this question has been answered for the distributed systems case.</p>

<p>Is there a set of canonical distributed systems problems from which all the possible distributed system problems can be reduced to? What is this canonical list?</p>

<p>If there is not a canonical list what is the current list of problems and what reductions exist?</p>

<p>For example, I would say very naively that the leader election and mutual exclusion problems can be reduced to the consensus problem. I would also say that a distributed snapshot can be reduced to a distributed clock. It it true or plain wrong? </p>

<p>If possible, I would prefer that the answers provide a reference to a published paper/book supporting its claims :)</p>

CC BY-SA 3.0
2013-04-03T20:24:08.017Z
[Copy](http://cs.stackexchange.com/questions/10878/is-there-a-list-of-canonical-problems-in-distributed-systems) on [cs.se]
Kaveh
<reductions><dc.distributed-comp><concurrency>
Is there a list of canonical problems in distributed systems?
marcmagransdeabril
# Is there a list of canonical problems in distributed systems?

(Asked by: username_0 on 2013-04-03)

Last week, I was reading again Leslie's Lamport's 1982 trasncript of a conference he gave about [Solved Problems, Unsolved Problems and Non-Problems in Concurrency](http://research.microsoft.com/en-us/um/people/lamport/pubs/solved-and-unsolved.pdf). The paper is easily readable, but one of the things that got me thinking is the following assertion:

> Can any problem be regarded as a mutual exclusion problem or a
> producer- consumer problem, or a combination of the two?

I would like to know if this question has been answered for the distributed systems case.

Is there a set of canonical distributed systems problems from which all the possible distributed system problems can be reduced to? What is this canonical list?

If there is not a canonical list what is the current list of problems and what reductions exist?

For example, I would say very naively that the leader election and mutual exclusion problems can be reduced to the consensus problem. I would also say that a distributed snapshot can be reduced to a distributed clock. It it true or plain wrong?

If possible, I would prefer that the answers provide a reference to a published paper/book supporting its claims :)

**Tags:** reductions, dc.distributed-comp, concurrency
> **Comments:**
> **username_1**: [Copy](http://cs.stackexchange.com/questions/10878/is-there-a-list-of-canonical-problems-in-distributed-systems) on [cs.se]  

---

## 1 answers

### Answer by username_2 on 2013-04-04. Score: 9 | Accepted answer

> Is there a set of canonical distributed systems problems from which all the possible distributed system problems can be reduced to?

I'm unaware of such a published list of problems.

Keep in mind that there are *many* different (and somewhat incomparable) models in distributed computing, ranging from the "benign" synchronous (fault-free) model where nodes execute in lock-step rounds and all messages are delivered
reliably in each round, to the asynchronous model where there are no bounds on
processing speeds and message delays and nodes themselves might crash or send
corrupted messages.
To further add to this variety, there are other requirements and assumptions
that are orthogonal to synchrony and faults: the initial knowledge of nodes
(network size, diameter of the network, maximum node degree, etc.), the ability
to query a failure detectors, whether nodes have unique identifiers, atomicity
of send & receive steps, the maximum size of a single message, and many more.

The actual model at hand often implies a very different nature of
question. (See [1] for more elaboration on these $2$ sub-communities in distributed computing.)
In models that are close to the fault-free synchronous model, researchers often
look at the complexity of local computation, for example, *"What is the time and message
complexity for computing a vertex coloring?"*

When looking at failures on the other hand, the questions are more related to solvability issues like *"Is consensus solvable in this model?"* or *"Can we implement this fancy
failure detector under these assumptions?"*

> If there is not a canonical list what is the current list of problems and what reductions exist?

There are many examples of such reductions in certain distributed computing
models, I'll limit my answer to the following 2:

## Local computation in the (fault-free) synchronous model

[2] show reductions between many optimization problems, for example, Minimum Dominating
Set, Maximal Independent Set (MIS), Maximal Matching (MM), and Minimum Vertex
Cover (MVC): In particular, [2] show a lower bound of $\Omega(\sqrt{\log n} +
\log\Delta)$, where $n$ is the network size and $\Delta$ the max degree, for
computing a constant approximation of an MVC. From this, the same bound follows
for computing an MM, since any maximal matching is also a $2$-approximation of
an MVC. From this, you also get a bound on computing an MIS, because an
MIS-algorithm $A$ can be used to compute MM by simulating the execution of $A$
on the line graph.

## Asynchronous Model with Crash Failures

Here the most studied problem is
fault-tolerant consensus and its many variations, since implementing basic primitives like atomic broadcast and or a synchronizer themselves require consensus.

For example, assuming access to failure detectors [3], gives rise to a classification of problems by looking at
the power of their respective failure detector.
We say that failure detector $S$ is the *weakest failure detector for problem* $P$, if, given any failure detector $T$ for $P$, you can also implement $S$.

Using this relation, we can define problem $P$ as being *harder* than problem $Q$, if
the weakest failure detector for solving $P$ can implement the weakest failure
detector for solving $Q$.
It has recently been shown that *every* problem has a weakest failure detector [4]; note however, that [4] is an existential result. For some problems, e.g., consensus, the weakest failure detector is known [5], while for other problems, e.g., $k$-set agreement, the weakest falure detector is still open [6].

> For example, I would say very naively that the leader election and mutual
> exclusion problems can be reduced to the consensus problem.

Sure, if you can solve consensus, you immediately have an algorithm for leader
election: Simply use the ID of each node as the input for the consensus
algorithm. The opposite way only holds in models where it is guaranteed that the leader is eventually known to all.

[1] Pierre Fraigniaud: Distributed computational complexities: are you volvo-addicted or nascar-obsessed? PODC 2010.
<http://doi.acm.org/10.1145/1835698.1835700>

[2] Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer: Local Computation: Lower and Upper Bounds. CoRR abs/1011.5470 (2010)
<http://arxiv.org/abs/1011.5470>

[3] Tushar Deepak Chandra, Sam Toueg: Unreliable Failure Detectors for Reliable Distributed Systems. J. ACM 43(2): 225-267 (1996).
<http://doi.acm.org/10.1145/226643.226647>

[4] Prasad Jayanti, Sam Toueg: Every problem has a weakest failure detector. PODC 2008: 75-84.
<http://doi.acm.org/10.1145/1400751.1400763>

[5] Tushar Deepak Chandra, Vassos Hadzilacos, Sam Toueg: The Weakest Failure Detector for Solving Consensus. J. ACM 43(4): 685-722 (1996)
<http://doi.acm.org/10.1145/234533.234549>

[6] Michel Raynal: Failure Detectors to Solve Asynchronous k-Set Agreement: a Glimpse of Recent Results. Bulletin of the EATCS 103: 74-95 (2011)
<http://albcom.lsi.upc.edu/ojs/index.php/beatcs/article/view/61>

> **Comments:**
> **username_1**: Hagit Attiya and Faith Ellen have an upcoming book titled "Impossibility Results for Distributed Computing".  

---

