2026-07-23T17:29:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25178 2026-03-19T12:59:14Z ddc:004 open_access

Tight Conditions for Binary-Output Tasks Under Crashes Albouy, Timothé Fernández Anta, Antonio Georgiou, Chryssis Nicolaou, Nicolas Wang, Junlang Distributed solvability Asynchrony Synchrony Impossibility proofs Binary-output tasks Crash tolerance Disagreement 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Timothé Albouy and Antonio Fernández Anta and Chryssis Georgiou and Nicolas Nicolaou and Junlang Wang 2026 Is Part Of LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2025.5 urn:nbn:de:0030-drops-251786 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.5 eng https://creativecommons.org/licenses/by/4.0/legalcode