Limited-use atomic snapshots with polylogarithmic step complexity

DOI10.1145/2732263MaRDI QIDQ5501949zbMATH OpenOpenAlexFDO

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

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

atomic snapshotconcurrent objectsgeneralized countersrestricted-use objects

Mathematics Subject Classification ID

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

Recommendations

• Faster than optimal snapshots (for a while), preliminary version
• Atomic Snapshots in O (n log n) Operations
• The complexity of updating snapshot objects
• Atomic snapshots from small registers
• Complexity tradeoffs for read and update operations

Cites work

• Adaptive and efficient algorithms for lattice agreement and renaming
• An optimal multi-writer snapshot algorithm
• Approximate shared-memory counting despite a strong adversary
• Are wait-free algorithms fast?
• Atomic Snapshots in O (n log n) Operations
• Atomic snapshots of shared memory
• Composite registers
• F-arrays, implementation and applications
• Immediate atomic snapshots and fast renaming
• Lower bounds for restricted-use objects
• Polylogarithmic concurrent data structures from monotone circuits
• SOFSEM 2005: Theory and Practice of Computer Science
• Time and Space Lower Bounds for Nonblocking Implementations
• Towards a practical snapshot algorithm

Cited in

(7)

• Faster than optimal snapshots (for a while), preliminary version
• Complexity tradeoffs for read and update operations
• Erratum to: ``Limited-use atomic snapshots with polylogarithmic step complexity
• Long-lived and adaptive atomic snapshot and immediate snapshot (extended abstract)
• Atomic snapshots from small registers
• Set-linearizable implementations from read/write operations: sets, fetch \& increment, stacks and queues with multiplicity
• Relaxed queues and stacks from read/write operations

This page was built for publication: Limited-use atomic snapshots with polylogarithmic step complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5501949)