Time-space tradeoffs for implementations of snapshots

DOI10.1145/1132516.1132542MaRDI QIDQ2931381zbMATH OpenOpenAlexFDO

Authors Panagiota Fatourou, Eric Ruppert, Faith E. Fich

Publication date 25 November 2014

Published in Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

anonymous processesdistributed computinglower boundshared memorysnapshottime-space tradeoffwait-free

Mathematics Subject Classification ID

Distributed systems (68M14) Data structures (68P05) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Time lower bounds for implementations of multi-writer snapshots
• The time complexity of updating snapshot memories
• Towards a practical snapshot algorithm
• On the memory overhead of distributed snapshots
• Time-optimal, space-efficient single-scanner snapshots \& multi-scanner snapshots using CAS
• Linear-time snapshot implementations in unbalanced systems
• A tight time lower bound for space-optimal implementations of multi-writer snapshots
• Efficient synchronous snapshots

Cited in

(19)

• Minimizing time-space cost for database version control
• Anonymous and fault-tolerant shared-memory computing
• Consistency as a branching time notion
• Lower and upper bounds for single-scanner snapshot implementations
• The time complexity of updating snapshot memories
• On the time complexity of minimum and maximum global snapshot problems
• Progress-space tradeoffs in single-writer memory implementations
• Of concurrent data structures and iterations
• The space complexity of unbounded timestamps
• Time lower bounds for implementations of multi-writer snapshots
• A tight time lower bound for space-optimal implementations of multi-writer snapshots
• On the memory overhead of distributed snapshots
• Time-Lapse Snapshots
• Linear space bootstrap communication schemes
• Linear-time snapshot implementations in unbalanced systems
• Space-optimal multi-writer snapshot objects are slow
• Long-lived and adaptive atomic snapshot and immediate snapshot (extended abstract)
• Efficient synchronous snapshots
• The complexity of updating snapshot objects

This page was built for publication: Time-space tradeoffs for implementations of snapshots

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