The complexity of updating multi-writer snapshot objects

DOI10.1145/1281100.1281151zbMATH Open1283.68152OpenAlexW2032236979MaRDI QIDQ5401435FDOQ5401435

Authors: Hagit Attiya, Fiath Ellen, Panagiota Fatourou 

Publication date: 13 March 2014

Published in: Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing (Search for Journal in Brave)

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

Recommendations

• The complexity of updating snapshot objects
• Space-optimal multi-writer snapshot objects are slow
• A tight time lower bound for space-optimal implementations of multi-writer snapshots
• Time lower bounds for implementations of multi-writer snapshots
• Single-scanner multi-writer snapshot implementations are fast!

zbMATH Keywords

distributed computingsnapshotlower boundshared memoryupdate

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed systems (68M14)

Cited In (6)

• Time lower bounds for implementations of multi-writer snapshots
• A tight time lower bound for space-optimal implementations of multi-writer snapshots
• Space-optimal multi-writer snapshot objects are slow
• Intermediate value linearizability: a quantitative correctness criterion
• The complexity of updating snapshot objects
• Inherent limitations on disjoint-access parallel implementations of transactional memory

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

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