Wait-free computing, and task checkability

This talk will provide an introduction to distributed shared-memory wait-free computing, including the way computation is captured by a model from algebraic topology. In essence, a task is wait-free solvable if and only if there is a simplicial mapping from a subdivision of the input complex I to the output complex O. The second part of the talk will deal with task checkability, where, given a task T and a black box protocol that claims to solve it, a distributed checker tries to find out whether the result of an execution is correct. We will show that the AND-checker is bounded to check only projection-closed tasks. For arbitrary checker, we will exhibit a tight bound on the minimum number of values to be used by the checker, as a function of the alternation number of the task T. The latter is defined as the length of the longest increasing sequence of simplexes in IxO that is alternating between correct and incorrect computations.

This is a joint work with Sergio Rajsbaum (UNAM, Mexico), and Corentin Travers (LaBRI, Bordeaux).