Faster than optimal snapshots (for a while), preliminary version

DOI10.1145/2332432.2332507MaRDI QIDQ2933814zbMATH OpenOpenAlexFDO

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

Publication date 5 December 2014

Published in Proceedings of the 2012 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

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

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) Distributed algorithms (68W15) Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.) (68N19)

Recommendations

• Limited-use atomic snapshots with polylogarithmic step complexity
• Time-optimal, space-efficient single-scanner snapshots \& multi-scanner snapshots using CAS
• Long-lived and adaptive atomic snapshot and immediate snapshot (extended abstract)
• Single-scanner multi-writer snapshot implementations are fast!
• Efficient synchronous snapshots

Cited in

(7)

• Limited-use atomic snapshots with polylogarithmic step complexity
• Atomic snapshots from small registers
• Lower bounds for restricted-use objects
• Towards a practical snapshot algorithm
• Tight bounds for asynchronous renaming
• Lower and upper bounds for single-scanner snapshot implementations
• The complexity of updating snapshot objects

This page was built for publication: Faster than optimal snapshots (for a while), preliminary version

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