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
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
distributed computinglower boundsshared memoryanonymityadopt-commitcovering argumentrandomized consensus
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15)
Cites Work
- Impossibility of distributed consensus with one faulty process
- Round-by-round fault detectors (extended abstract), unifying synchrony and asynchrony
- On the space complexity of randomized synchronization
- A layered analysis of consensus
- The Combined Power of Conditions and Information on Failures to Solve Asynchronous Set Agreement
- A short proof of Sperner's lemma
- Efficient low-contention asynchronous consensus with the value-oblivious adversary scheduler
- Relationships between broadcast and shared memory in reliable anonymous distributed systems
- Polylog randomized wait-free consensus
- Tight bounds for asynchronous randomized consensus
- Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement
- Approximate shared-memory counting despite a strong adversary
- A modular approach to shared-memory consensus, with applications to the probabilistic-write model
- Efficient asynchronous consensus with the weak adversary scheduler
- Lower bounds for randomized consensus under a weak adversary
Cited In (10)
- A complexity-based classification for multiprocessor synchronization
- On the complexity of basic abstractions to implement consensus
- Allocate-on-use space complexity of shared-memory algorithms
- On the uncontended complexity of anonymous agreement
- Concurrent use of write-once memory
- Locality and checkability in wait-free computing
- Tasks in modular proofs of concurrent algorithms
- Agreeing within a few writes
- Faster randomized consensus with an oblivious adversary
- Tasks in modular proofs of concurrent 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)
