The asynchronous computability theorem for t-resilient tasks

DOI10.1145/167088.167125zbMath1310.68079OpenAlexW1965990175MaRDI QIDQ5248477

Nir Shavit, Maurice P. Herlihy

Publication date: 7 May 2015

Published in: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/167088.167125

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Related Items (24)

An algorithmic approach to the asynchronous computability theorem ⋮ On the weakest failure detector ever ⋮ Geometric and combinatorial views on asynchronous computability ⋮ A computationally intractable problem on simplicial complexes ⋮ Communication pattern logic: epistemic and topological views ⋮ Iterated chromatic subdivisions are collapsible ⋮ Wait-free computing ⋮ Renaming and the weakest family of failure detectors ⋮ On the Validity of Consensus ⋮ On the importance of having an identity or, is consensus really universal? ⋮ Closed schedulers: a novel technique for analyzing asynchronous protocols ⋮ The BG distributed simulation algorithm ⋮ Long lived adaptive splitter and applications ⋮ The gap in circumventing the impossibility of consensus ⋮ On set consensus numbers ⋮ Tight bounds on the round complexity of distributed 1-solvable tasks ⋮ An Introduction to the Topological Theory of Distributed Computing with Safe-consensus ⋮ Algebraic topology and concurrency ⋮ New combinatorial topology bounds for renaming: the lower bound ⋮ Towards a practical snapshot algorithm ⋮ Wait-free approximate agreement on graphs ⋮ A topological perspective on distributed network algorithms ⋮ Wait-free implementations in message-passing systems ⋮ A classification of wait-free loop agreement tasks

This page was built for publication: The asynchronous computability theorem for t-resilient tasks