Atomic Snapshots in O (n log n) Operations

DOI10.1137/S0097539795279463zbMath0907.68053OpenAlexW2081960123MaRDI QIDQ4388875

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

linearizabilityasynchronous shared memory systemsatomic read/write registerssingle-reader multiwritersnapshot objectswait-free computations

Mathematics Subject Classification ID

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

Related Items (20)

Unnamed Item ⋮ Lower and upper bounds for single-scanner snapshot implementations ⋮ Power and limits of distributed computing shared memory models ⋮ Linear-time snapshot implementations in unbalanced systems ⋮ Of choices, failures and asynchrony: the many faces of set agreement ⋮ Interrupting snapshots and the \(\text{Java}^{\text{TM}}\) size method ⋮ The renaming problem in shared memory systems: an introduction ⋮ An adaptive collect algorithm with applications ⋮ Condition-based consensus solvability: a hierarchy of conditions and efficient protocols ⋮ The complexity of updating snapshot objects ⋮ Help when needed, but no more: efficient read/write partial snapshot ⋮ Set-constrained delivery broadcast: a communication abstraction for Read/write implementable distributed objects ⋮ An impossibility about failure detectors in the iterated immediate snapshot model ⋮ Unnamed Item ⋮ Towards a practical snapshot algorithm ⋮ Byzantine lattice agreement in synchronous message passing systems ⋮ Revisionist simulations: a new approach to proving space lower bounds ⋮ From adaptive renaming to set agreement ⋮ The F-Snapshot Problem ⋮ Limited-Use Atomic Snapshots with Polylogarithmic Step Complexity

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