The time complexity of updating snapshot memories

DOI10.1016/S0020-0190(97)00189-0MaRDI QIDQ293175zbMATH OpenOpenAlexFDO

Authors Amos Israeli, Asaf Shirazi

Publication date 9 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019097001890?np=y

zbMATH Keywords

lower boundfault tolerancedistributed protocolsnapshot memory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed systems (68M14)

Recommendations

• Linear-time snapshot implementations in unbalanced systems
• Efficient synchronous snapshots
• Time-space tradeoffs for implementations of snapshots
• Time-Lapse Snapshots
• The complexity of updating snapshot objects

Cites work

• Are wait-free algorithms fast?
• Atomic snapshots in O(n log n) operations
• Atomic snapshots of shared memory
• Atomic snapshots using lattice agreement
• Composite registers
• Linear-time snapshot implementations in unbalanced systems
• On interprocess communication. I: Basic formalism
• On interprocess communication. II: Algorithms
• Optimal multi-writer multi-reader atomic register
• The time complexity of updating snapshot memories
• Time-Lapse Snapshots

Cited in

(9)

• Linear-time snapshot implementations in unbalanced systems
• Time-space tradeoffs for implementations of snapshots
• Hundreds of impossibility results for distributed computing
• A CONSTANT TIME ALGORITHM FOR DNA ADD
• The complexity of updating snapshot objects
• Intermediate value linearizability: a quantitative correctness criterion
• The time complexity of updating snapshot memories
• Inherent limitations on disjoint-access parallel implementations of transactional memory
• The F-Snapshot Problem

This page was built for publication: The time complexity of updating snapshot memories

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