Space-optimal multi-writer snapshot objects are slow

DOI10.1145/571825.571828MaRDI QIDQ5170861zbMATH OpenOpenAlexFDO

Authors Panagiota Fatourou, Eric Ruppert, Faith E. Fich

Publication date 25 July 2014

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

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

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)

Recommendations

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

Cited in

(10)

• Solo-valency and the cost of coordination
• Lower and upper bounds for single-scanner snapshot implementations
• Time and space optimal implementations of atomic multi-writer register
• Time lower bounds for implementations of multi-writer snapshots
• A tight time lower bound for space-optimal implementations of multi-writer snapshots
• Linear space bootstrap communication schemes
• Hundreds of impossibility results for distributed computing
• Single-scanner multi-writer snapshot implementations are fast!
• The complexity of updating multi-writer snapshot objects
• The complexity of updating snapshot objects

This page was built for publication: Space-optimal multi-writer snapshot objects are slow

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