Lower and upper bounds for single-scanner snapshot implementations

DOI10.1007/S00446-016-0286-7MaRDI QIDQ2401677zbMATH OpenOpenAlexFDO

Authors Panagiota Fatourou, Nikolaos D. Kallimanis

Publication date 4 September 2017

Published in Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00446-016-0286-7

zbMATH Keywords

asynchronousatomic objectsdistributed algorithmslinearizabilitymulti-writershared memorysingle-scannersnapshotsstep optimal algorithmswait-freedom

Mathematics Subject Classification ID

Distributed systems (68M14) Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15)

Recommendations

• Single-scanner multi-writer snapshot implementations are fast!
• Time-optimal, space-efficient single-scanner snapshots \& multi-scanner snapshots using CAS
• A tight time lower bound for space-optimal implementations of multi-writer snapshots
• Space-optimal multi-writer snapshot objects are slow
• Faster than optimal snapshots (for a while), preliminary version

Cites work

• A tight time lower bound for space-optimal implementations of multi-writer snapshots
• An optimal multi-writer snapshot algorithm
• Are wait-free algorithms fast?
• Atomic Snapshots in O (n log n) Operations
• Atomic snapshots of shared memory
• Bounds on shared memory for mutual exclusion
• Composite registers
• Concurrent Reading While Writing
• F-arrays, implementation and applications
• Linear-time snapshot implementations in unbalanced systems
• On the space complexity of randomized synchronization
• Simple and efficient bounded concurrent timestamping and the traceable use abstraction
• Space-optimal multi-writer snapshot objects are slow
• The complexity of updating snapshot objects
• The concurrency hierarchy, and algorithms for unbounded concurrency
• Time and Space Lower Bounds for Nonblocking Implementations
• Time lower bounds for implementations of multi-writer snapshots
• Time-space tradeoffs for implementations of snapshots
• Towards a practical snapshot algorithm

Cited in

(4)

• A tight time lower bound for space-optimal implementations of multi-writer snapshots
• Single-scanner multi-writer snapshot implementations are fast!
• Time-optimal, space-efficient single-scanner snapshots \& multi-scanner snapshots using CAS
• The complexity of updating snapshot objects

This page was built for publication: Lower and upper bounds for single-scanner snapshot implementations

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