2026-07-22T06:26:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14837 2024-03-06T10:54:58Z ddc:004 open_access

VBR: Version Based Reclamation Sheffi, Gali Herlihy, Maurice Petrank, Erez Safe memory reclamation concurrency linearizability lock-freedom Safe lock-free memory reclamation is a difficult problem. Existing solutions follow three basic methods (or their combinations): epoch based reclamation, hazard pointers, and optimistic reclamation. Epoch-based methods are fast, but do not guarantee lock-freedom. Hazard pointer solutions are lock-free but typically do not provide high performance. Optimistic methods are lock-free and fast, but previous optimistic methods did not go all the way. While reads were executed optimistically, writes were protected by hazard pointers. In this work we present a new reclamation scheme called version based reclamation (VBR), which provides a full optimistic solution to lock-free memory reclamation, obtaining lock-freedom and high efficiency. Speculative execution is known as a fundamental tool for improving performance in various areas of computer science, and indeed evaluation with a lock-free linked-list, hash-table and skip-list shows that VBR outperforms state-of-the-art existing solutions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gali Sheffi and Maurice Herlihy and Erez Petrank 2021 Is Part Of LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2021.35 urn:nbn:de:0030-drops-148374 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.35 eng https://creativecommons.org/licenses/by/4.0/legalcode