Tight Conditions for Binary-Output Tasks under Crashes
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911212213633024 |
|---|---|
| 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 | This paper explores necessary and sufficient system conditions to solve distributed tasks with binary outputs (\textit{i.e.}, tasks with output values in $\{0,1\}$). We focus on the distinct output sets of values a task can produce (intentionally disregarding validity and value multiplicity), considering that some processes may output no value. In a distributed system with $n$ processes, of which up to $t \leq n$ can crash, we provide a complete characterization of the tight conditions on $n$ and $t$ under which every class of tasks with binary outputs is solvable, for both synchronous and asynchronous systems. This output-set approach yields highly general results: it unifies multiple distributed computing problems, such as binary consensus and symmetry breaking, and it produces impossibility proofs that hold for stronger task formulations, including those that consider validity, account for value multiplicity, or move beyond binary outputs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_13755 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tight Conditions for Binary-Output Tasks under Crashes Albouy, Timothé Anta, Antonio Fernández Georgiou, Chryssis Nicolaou, Nicolas Wang, Junlang Distributed, Parallel, and Cluster Computing This paper explores necessary and sufficient system conditions to solve distributed tasks with binary outputs (\textit{i.e.}, tasks with output values in $\{0,1\}$). We focus on the distinct output sets of values a task can produce (intentionally disregarding validity and value multiplicity), considering that some processes may output no value. In a distributed system with $n$ processes, of which up to $t \leq n$ can crash, we provide a complete characterization of the tight conditions on $n$ and $t$ under which every class of tasks with binary outputs is solvable, for both synchronous and asynchronous systems. This output-set approach yields highly general results: it unifies multiple distributed computing problems, such as binary consensus and symmetry breaking, and it produces impossibility proofs that hold for stronger task formulations, including those that consider validity, account for value multiplicity, or move beyond binary outputs. |
| title | Tight Conditions for Binary-Output Tasks under Crashes |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2510.13755 |