The ERA Theorem for Safe Memory Reclamation

DOI10.1145/3583668.3594564MaRDI QIDQ6202230zbMATH OpenOpenAlexWikidataFDO

Authors Erez Petrank

Publication date 26 March 2024

Published in Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

robustnessconcurrencylock-freedomsafe memory reclamation

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Abstract: Safe memory reclamation (SMR) schemes for concurrent data structures offer trade-offs between three desirable properties: ease of integration, robustness, and applicability. In this paper we rigorously define SMR and these three properties, and we present the ERA theorem, asserting that any SMR scheme can only provide at most two of the three properties.

Cites work

• scientific article; zbMATH DE number 2006660 (Why is no real title available?)
• Black-Box Concurrent Zero-Knowledge Requires (Almost) Logarithmically Many Rounds
• Impossibility of distributed consensus with one faulty process
• Lock-free reference counting
• Nesting-safe recoverable linearizability: modular constructions for non-volatile memory
• Upper and Lower Bounds on the Space Complexity of Detectable Objects
• Verifying concurrent memory reclamation algorithms with grace

This page was built for publication: The ERA Theorem for Safe Memory Reclamation

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