A generalized asynchronous computability theorem

DOI10.1145/2611462.2611477MaRDI QIDQ2943623zbMATH OpenOpenAlexFDO

Authors Eli Gafni, Petr Kuznetsov, Ciprian Manolescu

Publication date 3 September 2015

Published in Proceedings of the 2014 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.1220

zbMATH Keywords

asynchronous computabilitycharacterizationiterated modelstopology

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Abstract: We consider the models of distributed computation defined as subsets of the runs of the iterated immediate snapshot model. Given a task $T$ and a model $M$, we provide topological conditions for $T$ to be solvable in $M$. When applied to the wait-free model, our conditions result in the celebrated Asynchronous Computability Theorem (ACT) of Herlihy and Shavit. To demonstrate the utility of our characterization, we consider a task that has been shown earlier to admit only a very complex $t$-resilient solution. In contrast, our generalized computability theorem confirms its $t$-resilient solvability in a straightforward manner.

Recommendations

• Asynchronous computability theorems for \(t\)-resilient systems
• An asynchronous computability theorem for fair adversaries
• An algorithmic approach to the asynchronous computability theorem
• Toward a Topological Characterization of Asynchronous Complexity
• The topological structure of asynchronous computability

Cited in

(20)

• An algorithmic approach to the asynchronous computability theorem
• Asynchronous computability theorems for \(t\)-resilient systems
• From geometric semantics to asynchronous computability
• General decidability results for asynchronous shared-memory programs: higher-order and beyond
• A simple constructive computability theorem for wait-free computation
• t-resilient immediate snapshot Is impossible
• Schlegel diagram and optimizable immediate snapshot protocol
• Toward a Topological Characterization of Asynchronous Complexity
• The computational structure of progress conditions
• Power and limits of distributed computing shared memory models
• Back to the coordinated attack problem
• scientific article; zbMATH DE number 7438568 (Why is no real title available?)
• Sporadic solutions to zero-one exclusion tasks
• An asynchronous computability theorem for fair adversaries
• Distributed computability in Byzantine asynchronous systems
• A Sound Foundation for the Topological Approach to Task Solvability
• Brief announcement: On decidability of 2-process affine models
• The combinatorial structure of wait-free solvable tasks (extended abstract)
• Algebraic topology and distributed computing
• Topological characterization of consensus in distributed systems

This page was built for publication: A generalized asynchronous computability theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2943623)