The topological structure of asynchronous computability

1999/11/01 by Maurice Herlihy, Nir Shavit · 25 citations
Computer Science · #Distributed systems and fault tolerance #Computability, Logic, AI Algorithms #Interconnection Networks and Systems

paper · pdf · doi:10.1145/331524.331529

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.

Citations

• Impossibility of distributed consensus with one faulty process

Cited by

• Anonymous Obstruction-free (n,k)-Set Agreement with n-k+1 Atomic Read/Write Registers
• Space Bounds for Adaptive Renaming
• Standard protocol complexes for the immediate snapshot read/write model
• On Decidability of 2-process Affine Models
• Local generation of languages
• A General Input-Dependent Colorless Computability Theorem and Applications to Core-Dependent Adversaries
• Stone Duality Proofs for Colorless Distributed Computability Theorems
• Set Consensus: Captured by a Set of Runs with Ramifications
• Tight Conditions for Binary-Output Tasks under Crashes
• Tight Bounds for Connectivity and Set Agreement in Byzantine Synchronous Systems
• Schlegel Diagram and Optimizable Immediate Snapshot Protocol
• Space-Time Trade-off in Bounded Iterated Memory
• An Equivariance Theorem with Applications to Renaming (Preliminary Version)
• Asynchronous Exclusive Selection
• A generalized asynchronous computability theorem
• Distributed Computability in Byzantine Asynchronous Systems
• The Topology of Local Computing in Networks
• t-Resilient k-Immediate Snapshot and its Relation with Agreement Problems
• Fully Anonymous Shared Memory Algorithms
• Continuous Tasks and the Chromatic Simplicial Approximation Theorem
• Asynchrony from Synchrony
• Synchronous Hybrid Message-Adversary
• A simplicial complex model of dynamic epistemic logic for fault-tolerant distributed computing
• Shortest Paths in a Weighted Simplicial Complex
• A topological characterization of stabilizing consensus. [europepmc]

Related

• An Algorithmic Approach to the Asynchronous Computability Theorem
• The read/write protocol complex is collapsible
• A generalized asynchronous computability theorem
• Topological Characterization of Task Solvability in General Models of Computation
• An Asynchronous Computability Theorem for Fair Adversaries