On the Decidability of Distributed Tasks with Output Sets under Asynchrony and Any Number of Crashes
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908947562102784 |
|---|---|
| author | Albouy, Timothé Anta, Antonio Fernández Georgiou, Chryssis Nicolaou, Nicolas Wang, Junlang |
| author_facet | Albouy, Timothé Anta, Antonio Fernández Georgiou, Chryssis Nicolaou, Nicolas Wang, Junlang |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_06920 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the Decidability of Distributed Tasks with Output Sets under Asynchrony and Any Number of Crashes Albouy, Timothé Anta, Antonio Fernández Georgiou, Chryssis Nicolaou, Nicolas Wang, Junlang Distributed, Parallel, and Cluster Computing 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. |
| title | On the Decidability of Distributed Tasks with Output Sets under Asynchrony and Any Number of Crashes |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2604.06920 |