The complexity of updating snapshot objects

DOI10.1016/J.JPDC.2011.08.002MaRDI QIDQ663413zbMATH OpenOpenAlexFDO

Authors Hagit Attiya, Faith Ellen, Panagiota Fatourou

Publication date 14 February 2012

Published in Journal of Parallel and Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jpdc.2011.08.002

zbMATH Keywords

lower boundssnapshotsupdates

Mathematics Subject Classification ID

Distributed systems (68M14) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15)

Recommendations

• The complexity of updating multi-writer snapshot objects
• Space-optimal multi-writer snapshot objects are slow
• A tight time lower bound for space-optimal implementations of multi-writer snapshots
• Lower and upper bounds for single-scanner snapshot implementations
• Faster than optimal snapshots (for a while), preliminary version

Cites work

• A tight time lower bound for space-optimal implementations of multi-writer snapshots
• Adaptive and efficient algorithms for lattice agreement and renaming
• An optimal multi-writer snapshot algorithm
• Atomic Snapshots in O (n log n) Operations
• Atomic snapshots of shared memory
• Composite registers
• F-arrays, implementation and applications
• scientific article; zbMATH DE number 996442 (Why is no real title available?)
• scientific article; zbMATH DE number 1179121 (Why is no real title available?)
• Inherent limitations on disjoint-access parallel implementations of transactional memory
• Linear-time snapshot implementations in unbalanced systems
• On the space complexity of randomized synchronization
• Randomized wait-free concurrent objects (extended abstract)
• Single-scanner multi-writer snapshot implementations are fast!
• SOFSEM 2005: Theory and Practice of Computer Science
• The time complexity of updating snapshot memories
• Time and Space Lower Bounds for Nonblocking Implementations
• Time lower bounds for implementations of multi-writer snapshots
• Time-Lapse Snapshots
• Time-optimal, space-efficient single-scanner snapshots \& multi-scanner snapshots using CAS
• Time-space tradeoffs for implementations of snapshots
• Towards a practical snapshot algorithm

Cited in

(6)

• Lower and upper bounds for single-scanner snapshot implementations
• The time complexity of updating snapshot memories
• Complexity tradeoffs for read and update operations
• What can be computed in a distributed system?
• The complexity of updating multi-writer snapshot objects
• Limited-use atomic snapshots with polylogarithmic step complexity

This page was built for publication: The complexity of updating snapshot objects

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