The time complexity of updating snapshot memories

DOI10.1016/S0020-0190(97)00189-0zbMath1339.68022OpenAlexW2065344737MaRDI QIDQ293175

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) Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Related Items (7)

The time complexity of updating snapshot memories ⋮ Linear-time snapshot implementations in unbalanced systems ⋮ Hundreds of impossibility results for distributed computing ⋮ The complexity of updating snapshot objects ⋮ Inherent limitations on disjoint-access parallel implementations of transactional memory ⋮ A CONSTANT TIME ALGORITHM FOR DNA ADD ⋮ The F-Snapshot Problem

Cites Work

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

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