The Topological Structure of Asynchronous Computability

Abstract We give necessary and sufficient combinatorial conditions characterizing the class of decision tasks that can be solved in a wait-free manner by asynchronous processes that communicate by reading and writing a shared memory. We introduce a new formalism for tasks, based on notions from classical algebraic and combinatorial topology, in which a task's possible input and output values are each associated with high-dimensional geometric structures called simplicial complexes. We characterize computability in terms of the topological properties of these complexes. This characterization has a surprising geometric interpretation: a task is solvable if and only if the complex representing the task's allowable inputs can be mapped to the complex representing the task's allowable outputs by a function satisfying certain simple regularity properties. Our formalism thus replaces the "operational " notion of a wait-free decision task, expressed in terms of interleaved computations unfolding in time, by a static "combinatorial " description expressed in terms of relations among topological spaces. This allows us to exploit powerful theorems from the classic literature on algebraic and combinatorial topology. The approach yields the first impossibility results for several long-standing open problems in distributed computing, such as the "renaming " problem of Attiya et al., and the "k-set agreement " problem of Chaudhuri. Preliminary versions of these results appeared in the 1993 and 1994 Symposiums on Theory of Computing [28, 29]