Limited-Use Atomic Snapshots with Polylogarithmic Step Complexity

DOI10.1145/2732263zbMath1321.68270OpenAlexW2034956448MaRDI QIDQ5501949

James Aspnes, Faith Ellen, Hagit Attiya, Keren Censor-Hillel

Publication date: 14 August 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2732263

zbMATH Keywords

concurrent objectsatomic snapshotrestricted-use objectsgeneralized counters

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items (1)

Set-linearizable implementations from read/write operations: sets, fetch \& increment, stacks and queues with multiplicity

Cites Work

• Composite registers
• Adaptive and Efficient Algorithms for Lattice Agreement and Renaming
• Lower Bounds for Restricted-Use Objects
• Approximate shared-memory counting despite a strong adversary
• An optimal multi-writer snapshot algorithm
• Atomic snapshots of shared memory
• Are wait-free algorithms fast?
• Atomic Snapshots in O (n log n) Operations
• Time and Space Lower Bounds for Nonblocking Implementations
• f -arrays
• Immediate atomic snapshots and fast renaming
• Polylogarithmic concurrent data structures from monotone circuits
• SOFSEM 2005: Theory and Practice of Computer Science
• Towards a practical snapshot algorithm

This page was built for publication: Limited-Use Atomic Snapshots with Polylogarithmic Step Complexity