On the Decidability of Distributed Tasks with Output Sets under Asynchrony and Any Number of Crashes
This work addresses foundational issues in distributed computing by providing a decision procedure for task solvability, which is incremental as it builds on existing theory but introduces a new task class and insights.
The paper tackles the problem of determining solvability for a new class of distributed tasks called SOS tasks under asynchrony and crashes, showing that such tasks are decidable with a connectivity-based rule, and it reveals that k-set agreement is solvable for k>1 under any number of crashes without validity, while consensus is not.
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.