A generalized asynchronous computability theorem

Abstract. We consider the models of distributed computation defined as subsets of the runs of the iterated immediate snapshot model. Given a task T and a model M, we provide topological conditions for T to be solvable in M. When applied to the wait-free model, our conditions result in the celebrated Asynchronous Computability Theorem (ACT) of Herlihy and Shavit. To demonstrate the utility of our characterization, we consider a task that has been shown earlier to admit a very complex t-resilient solution. In contrast, our generalized computability theorem confirms its t-resilient solvability in a straightforward manner. 1