Brief Announcement: Solvability of Three-Process General Tasks
Hagit Attiya, Pierre Fraigniaud, Ami Paz, Sergio Rajsbaum ยท HAL (Le Centre pour la Communication Scientifique Directe) ยท 2024
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 ฮ'.