Treffer: Solvability Characterization for General Three-Process Tasks

International audience ; A key result of distributed computing in asynchronous systems is a characterization for the wait-free solvability of colorless tasks by the existence of a continuous map from the task’s input complex (representing the valid input configurations) to its output complex (representing the valid output configurations) which respects that task’s specification. This natural characterization led to many proofs, mainly of impossibility: showing that a colorless task is not wait-free solvable, can be done by proving that there is no continuous map (respecting the task’s specification) between two simplicial complexes, which can be done using classical topological machinery.The seminal work of Herlihy and Shavit (JACM ’99) characterized the solvability of general (not necessarily colorless) tasks. However, this characterization is much more involved than the colorless one, as it uses the new notions of chromatic subdivisions and color-preserving maps. The characterization asks whether there exists a chromatic subdivision of the input complex and a color-preserving map from the resulting subdivided complex to the output complex. This characterization is much harder to check as there are no ready-made topological tools for it, and in fact, finding such a subdivision and map is related to finding an algorithm for the task. This work presents a new and simpler characterization for the solvability of general tasks with three processes. In our characterization, the output complex undergoes a bounded number of simple combinatorial transformations. Then, we check if there is a continuous map from the input complex to the resulting output complex; we show that this suffices for determining whether the original task is solvable. Our approach provides a new and more direct way for deciding the solvability of a task, and also for proving impossibility and possibility of wait-free solutions for general tasks.