babylonpolice.com

The famous asynchronous computability theorem (ACT) relates the existence of
an asynchronous wait-free shared memory protocol for solving a task with the
existence of a simplicial map from a subdivision of the simplicial complex
representing the inputs to the simplicial complex representing the allowable
outputs. The original theorem relies on a correspondence between protocols and
simplicial maps in round-structured models of computation that induce a compact
topology. This correspondence, however, is far from obvious for computation
models that induce a non-compact topology, and indeed previous attempts to
extend the ACT have failed.

This paper shows that in every non-compact model, protocols solving tasks
correspond to simplicial maps that need to be continuous. It first proves a
generalized ACT for sub-IIS models, some of which are non-compact, and applies
it to the set agreement task. Then it proves that in general models too,
protocols are simplicial maps that need to be continuous, hence showing that
the topological approach is universal. Finally, it shows that the approach used
in ACT that equates protocols and simplicial complexes actually works for every
compact model.

Our study combines, for the first time, combinatorial and point-set
topological aspects of the executions admitted by the computation model.