The computational structure of progress conditions and shared objects

DOI10.1007/S00446-019-00356-0MaRDI QIDQ1988520zbMATH OpenOpenAlexWikidataFDO

Authors Gadi Taubenfeld

Publication date 23 April 2020

Published in Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00446-019-00356-0

zbMATH Keywords

consensussynchronizationuniversalityshared objectswait-freedomwait-free hierarchy\(k\)-obstruction-freedom\(S\)-freedompower hierarchyprogress conditions

Mathematics Subject Classification ID

Distributed systems (68M14)

Recommendations

• The computational structure of progress conditions
• Determining Consensus Numbers
• On asymmetric progress conditions
• Solvability of Consensus: Composition Breaks Down for NonDeterministic Types
• Power and limits of distributed computing shared memory models

Cites work

• All of Us Are Smarter than Any of Us: Nondeterministic Wait-Free Hierarchies Are Not Robust
• Contention-Sensitive Data Structures and Algorithms
• Contention-sensitive data structures and algorithms
• Coordination without prior agreement
• Deterministic objects: life beyond consensus
• Distributed Computing
• Distributed Computing
• Distributed universality
• Failure detectors as type boosters
• Hundreds of impossibility results for distributed computing
• Impossibility of distributed consensus with one faulty process
• On asymmetric progress conditions
• On the nonexistence of resilient consensus protocols
• On the uncontended complexity of consensus
• Reaching Agreement in the Presence of Faults
• Resilient consensus for infinitely many processes. (Extended abstract)
• Robust wait-free hierarchies
• Safety-liveness exclusion in distributed computing
• Set agreement power is not a precise characterization for oblivious deterministic anonymous objects
• The computational structure of progress conditions
• The concurrency hierarchy, and algorithms for unbounded concurrency
• The disagreement power of an adversary
• The topology of distributed adversaries
• The weakest failure detectors to boost obstruction-freedom
• Timeliness-based wait-freedom, a gracefully degrading progress condition
• Toward a theory of transactional contention managers

Cited in

(3)

• The behavior of shared objects: Concept, pitfalls, and a new model
• The computational structure of progress conditions
• Compositional reasoning about active objects with shared futures

This page was built for publication: The computational structure of progress conditions and shared objects

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