13
$\begingroup$

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. 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 :)

$\endgroup$
9
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Hagit Attiya and Faith Ellen have an upcoming book titled "Impossibility Results for Distributed Computing". $\endgroup$ – Kaveh Apr 4 '13 at 4:04

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.