Atomic Snapshots in O (n log n) Operations

DOI10.1137/S0097539795279463zbMath0907.68053MaRDI 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

linearizability; asynchronous shared memory systems; atomic read/write registers; single-reader multiwriter; snapshot objects; wait-free computations

Mathematics Subject Classification ID

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

68W10: Parallel algorithms in computer science

68P05: Data structures

68W15: Distributed algorithms

Related Items

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