Tight bounds for asynchronous renaming
From MaRDI portal
Reliability, testing and fault tolerance of networks and computer systems (68M15) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Analysis of algorithms (68W40)
Recommendations
Cites work
- A partial equivalence between shared-memory and message-passing in an asynchronous fail-stop distributed environment
- A time complexity lower bound for adaptive mutual exclusion
- A time complexity lower bound for randomized implementations of some shared objects
- Adaptive and efficient algorithms for lattice agreement and renaming
- Adaptive and efficient mutual exclusion (extended abstract)
- Asynchronous exclusive selection
- Atomic snapshots of shared memory
- Constant-RMR implementations of CAS and other synchronization primitives using read and write operations
- Counting networks
- Distributed Computing
- Efficient adaptive collect using randomization
- Fast randomized test-and-set and renaming
- Faster than optimal snapshots (for a while), preliminary version
- Fully-Adaptive Algorithms for Long-Lived Renaming
- scientific article; zbMATH DE number 996442 (Why is no real title available?)
- scientific article; zbMATH DE number 5485533 (Why is no real title available?)
- scientific article; zbMATH DE number 1179121 (Why is no real title available?)
- Immediate atomic snapshots and fast renaming
- Introduction to algorithms.
- Linearizable implementations do not suffice for randomized distributed computation
- Mutual Exclusion with O(log^2 Log n) Amortized Work
- New combinatorial topology bounds for renaming: the lower bound
- New combinatorial topology bounds for renaming: the upper bound
- On the inherent weakness of conditional primitives
- Optimal-time adaptive strong renaming, with applications to counting
- Polylogarithmic concurrent data structures from monotone circuits
- Randomized wait-free concurrent objects (extended abstract)
- Reaching Agreement in the Presence of Faults
- Renaming in an asynchronous environment
- Strong order-preserving renaming in the synchronous message passing model
- Sublogarithmic test-and-set against a weak adversary
- The Complexity of Renaming
- The extended BG-simulation and the characterization of t-resiliency
- The Las-Vegas Processor Identity Problem (How and When to Be Unique)
- The processor identity problem
- The topological structure of asynchronous computability
- Time and Space Lower Bounds for Nonblocking Implementations
- Time bounds for decision problems in the presence of timing uncertainty and failures
- Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
- Wait-free algorithms for fast, long-lived renaming
- Wait-free implementations in message-passing systems
Cited in
(9)- Randomized consensus with regular registers
- Optimal-time adaptive strong renaming, with applications to counting
- Balls-into-leaves, sub-logarithmic renaming in synchronous message-passing systems
- Anonymous processors with synchronous shared memory: Monte Carlo algorithms
- Fast randomized test-and-set and renaming
- The renaming problem: recent developments and open questions
- Upper bound on the complexity of solving hard renaming
- Randomized loose renaming in \(O(\log \log n)\) time
- Brief announcement
This page was built for publication: Tight bounds for asynchronous renaming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3189653)
