Atomic Snapshots in O (n log n) Operations

DOI10.1137/S0097539795279463MaRDI QIDQ4388875zbMATH OpenOpenAlexFDO

Authors Hagit Attiya, Ophir Rachman

Publication date 10 May 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539795279463

zbMATH Keywords

asynchronous shared memory systemsatomic read/write registerslinearizabilitysingle-reader multiwritersnapshot objectswait-free computations

Mathematics Subject Classification ID

Data structures (68P05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Parallel algorithms in computer science (68W10) Distributed algorithms (68W15)

Recommendations

• Atomic snapshots of shared memory
• Efficient synchronous snapshots
• Atomic snapshots using lattice agreement
• Towards a practical snapshot algorithm

Cited in

(32)

• From adaptive renaming to set agreement
• Set-constrained delivery broadcast: a communication abstraction for read/write implementable distributed objects
• Composite registers
• Lower and upper bounds for single-scanner snapshot implementations
• Of choices, failures and asynchrony: the many faces of set agreement
• The F-Snapshot Problem
• Dynamic atomic snapshots
• scientific article; zbMATH DE number 7228882 (Why is no real title available?)
• A tight time lower bound for space-optimal implementations of multi-writer snapshots
• Help When Needed, But No More: Efficient Read/Write Partial Snapshot
• Power and limits of distributed computing shared memory models
• Atomic snapshots of shared memory
• Interrupting snapshots and the \(\text{Java}^{\text{TM}}\) size method
• Erratum to: ``Limited-use atomic snapshots with polylogarithmic step complexity
• The renaming problem in shared memory systems: an introduction
• Linear-time snapshot implementations in unbalanced systems
• Lattice agreement in message passing systems
• Atomic snapshots using lattice agreement
• An adaptive collect algorithm with applications
• Condition-based consensus solvability: a hierarchy of conditions and efficient protocols
• Long-lived and adaptive atomic snapshot and immediate snapshot (extended abstract)
• Atomic snapshots from small registers
• Efficient synchronous snapshots
• Limited-use atomic snapshots with polylogarithmic step complexity
• Towards a practical snapshot algorithm
• Byzantine lattice agreement in synchronous message passing systems
• Revisionist simulations: a new approach to proving space lower bounds
• The complexity of updating snapshot objects
• Help when needed, but no more: efficient read/write partial snapshot
• Optimal resilience in systems that mix shared memory and message passing
• Byzantine lattice agreement in asynchronous systems
• An impossibility about failure detectors in the iterated immediate snapshot model

This page was built for publication: Atomic Snapshots in O (n log n) Operations

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