2026-07-27T03:50:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21270 2024-10-24T07:40:09Z ddc:004 open_access

Brief Announcement: Solvability of Three-Process General Tasks Attiya, Hagit Fraigniaud, Pierre Paz, Ami Rajsbaum, Sergio Wait-free computing lower bounds topology The topological view on distributed computing represents a task T as a relation Δ between the complex ℐ of its inputs and the complex 𝒪 of its outputs. A cornerstone result in the field is an elegant computability characterization of the solvability of colorless tasks in terms of ℐ, 𝒪 and Δ. Essentially, a colorless task is wait-free solvable if and only if there is a continuous map from the geometric realization of ℐ to that of 𝒪 that respects Δ. This paper makes headway towards providing an analogous characterization for general tasks, which are not necessarily colorless, by concentrating on the case of three-process inputless tasks. Our key contribution is identifying local articulation points as an obstacle for the solvability of general tasks, and defining a topological deformation on the output complex of a task T, which eliminates these points by splitting them, to obtain a new task T', with an adjusted relation Δ' between the input complex ℐ and an output complex 𝒪' without articulation points. We obtain a new characterization of wait-free solvability of three-process general tasks: T is wait-free solvable if and only if there is a continuous map from the geometric realization of ℐ to that of 𝒪' that respects Δ'. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hagit Attiya and Pierre Fraigniaud and Ami Paz and Sergio Rajsbaum 2024 Is Part Of LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2024.42 urn:nbn:de:0030-drops-212700 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.42 eng https://creativecommons.org/licenses/by/4.0/legalcode