English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The famous asynchronous computability theorem (ACT) relates the existence ofan asynchronous wait-free shared memory protocol for solving a task with theexistence of a simplicial map from a subdivision of the simplicial complexrepresenting the inputs to the simplicial complex representing the allowableoutputs. The original theorem relies on a correspondence between protocols andsimplicial maps in round-structured models of computation that induce a compacttopology. This correspondence, however, is far from obvious for computationmodels that induce a non-compact topology, and indeed previous attempts toextend the ACT have failed.  This paper shows that in every non-compact model, protocols solving taskscorrespond to simplicial maps that need to be continuous. It first proves ageneralized ACT for sub-IIS models, some of which are non-compact, and appliesit to the set agreement task. Then it proves that in general models too,protocols are simplicial maps that need to be continuous, hence showing thatthe topological approach is universal. Finally, it shows that the approach usedin ACT that equates protocols and simplicial complexes actually works for everycompact model.  Our study combines, for the first time, combinatorial and point-settopological aspects of the executions admitted by the computation model.

Topological Characterization of Task Solvability in General Models of Computation