Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces Set of Output Sets (SOS) tasks, a new class of distributed tasks defined by the possible sets of output values. The authors prove that the solvability of SOS tasks under asynchronous execution with up to *t* crashes is decidable. Specifically, an SOS task is solvable if and only if its SOS graph (where nodes are output sets and edges represent subset relationships) is connected when *t* > 0.
Surprisingly, *k*-set agreement (for *k* > 1) is always solvable under asynchrony and any number of crashes when validity is not required, highlighting a stark contrast with the classic consensus problem.
In this paper, we define a new class of distributed tasks, called SOS tasks (for Set of Output Sets tasks), defined by the set $O$ of distinct output sets of values that can be produced. We then demonstrate that this class of tasks is decidable: there exists an effective procedure that determines whether any SOS task is solvable asynchronously under $t$ crashes. The decision rule is as follows. Every SOS task is solvable when $t=0$. For $t > 0$, an SOS task is solvable if and only if its SOS graph $G=(O,\subset)$ is connected. In this graph, each vertex is an output set in $O$, and two vertices are linked by an edge whenever one output set includes the other. One of the surprising implications of our results is that, without a validity property, $k$-set agreement is solvable under any number of crashes $t \geq 0$ for $k>1$, and unsolvable under $t >0$ crashes only for $k=1$ (consensus). Finally, we study a novel family of tasks called $d$-disagreement, which requires the system to always produce $d$ different output values, and we show that its implementability condition is related to the harmonic series.