The topological structure of asynchronous computability

1999477 citationsJournal Articlebronze Open Access

Authors

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.

Topics & Keywords

Distributed systems and fault tolerance Computability, Logic, AI Algorithms Interconnection Networks and Systems

Publication Details

Published in: Journal of the ACM

Volume 46, Issue 6, pp. 858-923

DOI: 10.1145/331524.331529

Field-Weighted Citation Impact: 8.10

Command Palette

The topological structure of asynchronous computability

Authors

Abstract

Topics & Keywords

Publication Details