The complexity of updating multi-writer snapshot objects

DOI10.1145/1281100.1281151MaRDI QIDQ5401435zbMATH OpenOpenAlexFDO

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

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)

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!

Cited in

(6)

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

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)