Tight Bounds for Asynchronous Renaming

DOI10.1145/2597630zbMath1295.68118OpenAlexW2057041531WikidataQ60019892 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

zbMATH Keywords

lower boundsdistributed computingshared memoryrenamingconcurrent data structures

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Related Items (2)

Anonymous Processors with Synchronous Shared Memory: Monte Carlo Algorithms ⋮ Randomized consensus with regular registers

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

This page was built for publication: Tight Bounds for Asynchronous Renaming