The space complexity of long-lived and one-shot timestamp implementations

DOI10.1145/1993806.1993826zbMath1321.68358arXiv1103.5794MaRDI QIDQ2943392

Lisa Higham, Philipp Woelfel, Eduardo Pacheco, Maryam Helmi

Publication date: 11 September 2015

Published in: Journal of the ACM, Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1103.5794

zbMATH Keywords

shared memory; space complexity; timestamps; obstruction-free; wait-free; solo-termination

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W05: Nonnumerical algorithms

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

68Q85: Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)