Tight bounds for adopt-commit objects

DOI10.1007/s00224-013-9448-1zbMath1314.68365OpenAlexW2005304136MaRDI QIDQ487260

Faith Ellen, James Aspnes

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

lower boundsdistributed computingshared memoryanonymityadopt-commitcovering argumentrandomized consensus

Mathematics Subject Classification ID

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

Related Items (9)

Agreeing within a few writes ⋮ On the uncontended complexity of anonymous agreement ⋮ Tasks in modular proofs of concurrent algorithms ⋮ Locality and checkability in wait-free computing ⋮ A complexity-based classification for multiprocessor synchronization ⋮ On the complexity of basic abstractions to implement consensus ⋮ Faster randomized consensus with an oblivious adversary ⋮ Allocate-On-Use Space Complexity of Shared-Memory Algorithms ⋮ Concurrent Use of Write-Once Memory

Cites Work

• Unnamed Item
• Efficient low-contention asynchronous consensus with the value-oblivious adversary scheduler
• Relationships between broadcast and shared memory in reliable anonymous distributed systems
• A Layered Analysis of Consensus
• Round-by-round fault detectors (extended abstract)
• Polylog randomized wait-free consensus
• On the space complexity of randomized synchronization
• The Combined Power of Conditions and Information on Failures to Solve Asynchronous Set Agreement
• Tight bounds for asynchronous randomized consensus
• Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement
• Impossibility of distributed consensus with one faulty process
• 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
• A short proof of Sperner's lemma

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