Tight Bounds for Asynchronous Renaming
From MaRDI portal
Publication:3189653
DOI10.1145/2597630zbMath1295.68118WikidataQ60019892 ScholiaQ60019892MaRDI QIDQ3189653
Keren Censor-Hillel, Seth Gilbert, Dan Alistarh, James Aspnes, Rachid Guerraoui
Publication date: 12 September 2014
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2597630
68W40: Analysis of algorithms
68Q85: Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68P05: Data structures
68M15: Reliability, testing and fault tolerance of networks and computer systems
Related Items
Randomized consensus with regular registers, Anonymous Processors with Synchronous Shared Memory: Monte Carlo Algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A time complexity lower bound for adaptive mutual exclusion
- Strong order-preserving renaming in the synchronous message passing model
- The processor identity problem
- New combinatorial topology bounds for renaming: the lower bound
- Wait-free implementations in message-passing systems
- Wait-free algorithms for fast, long-lived renaming
- Efficient adaptive collect using randomization
- On the inherent weakness of conditional primitives
- Adaptive and Efficient Algorithms for Lattice Agreement and Renaming
- A time complexity lower bound for randomized implementations of some shared objects
- Faster than optimal snapshots (for a while)
- Asynchronous exclusive selection
- Optimal-time adaptive strong renaming, with applications to counting
- Sub-logarithmic Test-and-Set against a Weak Adversary
- The topological structure of asynchronous computability
- Renaming in an asynchronous environment
- Fully-Adaptive Algorithms for Long-Lived Renaming
- Fast Randomized Test-and-Set and Renaming
- Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
- Reaching Agreement in the Presence of Faults
- A partial equivalence between shared-memory and message-passing in an asynchronous fail-stop distributed environment
- Atomic snapshots of shared memory
- Counting networks
- Time and Space Lower Bounds for Nonblocking Implementations
- The Las-Vegas Processor Identity Problem (How and When to Be Unique)
- The extended BG-simulation and the characterization of t-resiliency
- Adaptive and efficient mutual exclusion (extended abstract)
- Randomized wait-free concurrent objects (extended abstract)
- Immediate atomic snapshots and fast renaming
- Distributed Computing
- Polylogarithmic concurrent data structures from monotone circuits
- New combinatorial topology bounds for renaming
- Constant-RMR implementations of CAS and other synchronization primitives using read and write operations
- Linearizable implementations do not suffice for randomized distributed computation
- The Complexity of Renaming
- Mutual Exclusion with O(log^2 Log n) Amortized Work
- Time bounds for decision problems in the presence of timing uncertainty and failures
