This work 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.

About Junlang Wang

Junlang is a PhD student at IMDEA Networks Institute, where he works with the Global Computing Group. His research focuses on the theory of distributed systems. Junlang earned his BSc in Information Security from Xi’an University of Posts & Telecommunications, China and his MSc in Computer Systems and Networks from Chalmers University of Technology, Sweden.

Este evento se impartirá en inglés