2025/10/15 by Timothé Albouy, Albouy, Timothé, Antonio Fernández Anta +7
Computer Science · Decision Sciences · Engineering · #Distributed #FOS: Computer and information sciences #Parallel #Risk and Safety Analysis #Safety Systems Engineering in Autonomy #Software Reliability and Analysis Research #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2510.13755
openalex publication_date 2025/10/15 · openalex created_date 2025/10/17 · openalex updated_date 2026/07/28
This paper explores necessary and sufficient system conditions to solve distributed tasks with binary outputs (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 ≤ 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.