Prochain séminaire PPS: Jeudi 24 Mai, 11h, salle 1D23– Pierre Fraigniaud (LIAFA)

Le prochain séminaire PPS aura lieu Jeudi 24 Mai. Il sera donné par
Pierre Fraigniaud (LIAFA) et sera précédé, comme d'habitude, d'une
petite collation avec café, thé et croissants, servie dès 10h45 (même
salle).

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).