Tight bounds for adopt-commit objects
From MaRDI portal
Publication:487260
DOI10.1007/s00224-013-9448-1zbMath1314.68365MaRDI QIDQ487260
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
lower bounds; distributed computing; shared memory; anonymity; adopt-commit; covering argument; randomized consensus
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W15: Distributed algorithms
Related Items
Allocate-On-Use Space Complexity of Shared-Memory Algorithms, Faster randomized consensus with an oblivious adversary, Tasks in modular proofs of concurrent algorithms, On the complexity of basic abstractions to implement consensus, On the uncontended complexity of anonymous agreement, A complexity-based classification for multiprocessor synchronization, Locality and checkability in wait-free computing, Agreeing within a few writes, 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
