Eli Gafni: Generalized Asynchronous Computability Theorem

I'll review the asynchronous computability theorem (ACT) of Herlihy and Shavit

using the algorithmically slanted derivation of Borowsky and myself.

The theorem gives a necessary and sufficient condition on a task to be solvable

in the wait-free model of distributed computation.

 

I'll then explain a generalization of ACT (GACT), recently given by Kuznetsov, Manolescu and myself, that gives similarly flavored conditions of solvability for any model of computation comprised of subset of runs of the wait-free model. When GACT is applied to the wait free model it produces ACT.