Improved time bounds for linearizable implementations of abstract data types
From MaRDI portal
Publication:1627963
DOI10.1016/J.IC.2018.08.004zbMath1407.68313OpenAlexW2889895855MaRDI QIDQ1627963
Jiaqi Wang, Edward Talmage, Hyunyoung Lee, Jennifer Lundelius Welch
Publication date: 3 December 2018
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2018.08.004
Abstract data types; algebraic specification (68Q65) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed systems (68M14)
Related Items (3)
Brief Announcement: Improved, Partially-Tight Multiplicity Queue Lower Bounds ⋮ Relaxed data types as consistency conditions ⋮ Lower bounds on message passing implementations of multiplicity-relaxed queues and stacks
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- On the possibility and impossibility of achieving clock synchronization
- On interprocess communication. I: Basic formalism
- Easy impossibility proofs for distributed consensus problems
- Linearizable read/write objects
- Closed form bounds for clock synchronization under simple uncertainty assumptions
- Gradient clock synchronization
- Quantitative relaxation of concurrent data structures
- The Computability of Relaxed Data Structures: Queues and Stacks as Examples
- Tight bounds for clock synchronization
- An upper and lower bound for clock synchronization
- Efficiency of Synchronous Versus Asynchronous Distributed Systems
- Commutativity-based concurrency control for abstract data types
- Efficiency of semisynchronous versus asynchronous networks
- The Impact of Timing Knowledge on the Session Problem
- Optimal Clock Synchronization under Different Delay Assumptions
- Designing algorithms for distributed systems with partially synchronized clocks
This page was built for publication: Improved time bounds for linearizable implementations of abstract data types
