Tight bounds for adopt-commit objects

DOI10.1007/S00224-013-9448-1zbMATH Open1314.68365OpenAlexW2005304136MaRDI QIDQ487260FDOQ487260

Authors James Aspnes, Faith Ellen

Publication date 19 January 2015

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-013-9448-1

zbMATH Keywords

distributed computinglower boundsshared memoryanonymityadopt-commitcovering argumentrandomized consensus

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15)

Recommendations

• On the complexity of basic abstractions to implement consensus
• Lower bounds for adaptive collect and related objects
• A modular approach to shared-memory consensus, with applications to the probabilistic-write model
• A modular approach to shared-memory consensus, with applications to the probabilistic-write model
• Lower bounds for restricted-use objects

Cites work

• A layered analysis of consensus
• A modular approach to shared-memory consensus, with applications to the probabilistic-write model
• A short proof of Sperner's lemma
• Approximate shared-memory counting despite a strong adversary
• Efficient asynchronous consensus with the weak adversary scheduler
• Efficient low-contention asynchronous consensus with the value-oblivious adversary scheduler
• Impossibility of distributed consensus with one faulty process
• Lower bounds for randomized consensus under a weak adversary
• Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement
• On the space complexity of randomized synchronization
• Polylog randomized wait-free consensus
• Relationships between broadcast and shared memory in reliable anonymous distributed systems
• Round-by-round fault detectors (extended abstract), unifying synchrony and asynchrony
• The Combined Power of Conditions and Information on Failures to Solve Asynchronous Set Agreement
• Tight bounds for asynchronous randomized consensus

Cited in

(10)

• Tasks in modular proofs of concurrent algorithms
• Faster randomized consensus with an oblivious adversary
• A complexity-based classification for multiprocessor synchronization
• On the complexity of basic abstractions to implement consensus
• Locality and checkability in wait-free computing
• Concurrent use of write-once memory
• Tasks in modular proofs of concurrent algorithms
• Agreeing within a few writes
• On the uncontended complexity of anonymous agreement
• Allocate-on-use space complexity of shared-memory algorithms

This page was built for publication: Tight bounds for adopt-commit objects

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