Eli Gafni: Generalized Asynchronous Computability Theorem

Friday, September 19, 2014 - 1:00pm to 2:30pm
Location: 
32-G631
Speaker: 
Eli Gafni
Biography: 
UCLA
Abstract: 
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.