13 Search Results for "Petrank, Erez"

Document
DOI: 10.4230/LIPIcs.OPODIS.2025.17
Recoverable Lock-Free Locks

Authors: Hagit Attiya, Panagiota Fatourou, Eleftherios Kosmas, and Yuanhao Wei

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
This paper presents the first transformation that introduces both lock-freedom and recoverability. Our transformation starts with a lock-based implementation, and provides a recoverable, lock-free substitution to lock acquire and lock release operations. The transformation supports nested locks for generality and ensures recoverability without jeopardising the correctness of the lock-based implementation it is applied on.
Cite as

Hagit Attiya, Panagiota Fatourou, Eleftherios Kosmas, and Yuanhao Wei. Recoverable Lock-Free Locks. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 17:1-17:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{attiya_et_al:LIPIcs.OPODIS.2025.17,
  author =	{Attiya, Hagit and Fatourou, Panagiota and Kosmas, Eleftherios and Wei, Yuanhao},
  title =	{{Recoverable Lock-Free Locks}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{17:1--17:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.17},
  URN =		{urn:nbn:de:0030-drops-251905},
  doi =		{10.4230/LIPIcs.OPODIS.2025.17},
  annote =	{Keywords: recoverable computing, NVM, lock, lock-freedom}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2025.55
Brief Announcement: Concurrent Double-Ended Priority Queues

Authors: Panagiota Fatourou, Eric Ruppert, and Ioannis Xiradakis

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
This work provides the first concurrent implementation of a double-ended priority queue (DEPQ). We describe a general way to add an ExtractMax operation to any concurrent priority queue that already supports Insert and ExtractMin.
Cite as

Panagiota Fatourou, Eric Ruppert, and Ioannis Xiradakis. Brief Announcement: Concurrent Double-Ended Priority Queues. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 55:1-55:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fatourou_et_al:LIPIcs.DISC.2025.55,
  author =	{Fatourou, Panagiota and Ruppert, Eric and Xiradakis, Ioannis},
  title =	{{Brief Announcement: Concurrent Double-Ended Priority Queues}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{55:1--55:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.55},
  URN =		{urn:nbn:de:0030-drops-248719},
  doi =		{10.4230/LIPIcs.DISC.2025.55},
  annote =	{Keywords: shared-memory, data structure, double-ended, priority queue, priority deque, heap, skip list, combining}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.35
PIPQ: Strict Insert-Optimized Concurrent Priority Queue

Authors: Olivia Grimes, Ahmed Hassan, Panagiota Fatourou, and Roberto Palmieri

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
This paper presents PIPQ, a strict and linearizable concurrent priority queue whose design differs from existing solutions in literature because it focuses on enabling parallelism of insert operations as opposed to accelerating delete-min operations, as traditionally done. In a nutshell, PIPQ’s structure includes two levels: the worker level and the leader level. The worker level provides per-thread data structures enabling fast and parallel insertions. The leader level contains the highest priority elements in the priority queue and can thus serve delete-min operations. Our evaluation, which includes an exploration of different data access patterns, operation mixes, runtime settings, and an integration into a graph-based application, shows that PIPQ outperforms competitors in a variety of cases, especially with insert-dominant workloads.
Cite as

Olivia Grimes, Ahmed Hassan, Panagiota Fatourou, and Roberto Palmieri. PIPQ: Strict Insert-Optimized Concurrent Priority Queue. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 35:1-35:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{grimes_et_al:LIPIcs.DISC.2025.35,
  author =	{Grimes, Olivia and Hassan, Ahmed and Fatourou, Panagiota and Palmieri, Roberto},
  title =	{{PIPQ: Strict Insert-Optimized Concurrent Priority Queue}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{35:1--35:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.35},
  URN =		{urn:nbn:de:0030-drops-248525},
  doi =		{10.4230/LIPIcs.DISC.2025.35},
  annote =	{Keywords: Priority Queue, Concurrent Data Structures, Synchronization}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.74
Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications

Authors: Paweł Gawrychowski, Egor Gorbachev, and Tomasz Kociumaka

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Min-plus matrix multiplication is a fundamental tool for designing algorithms operating on distances in graphs and different problems solvable by dynamic programming. We know that, assuming the APSP hypothesis, no subcubic-time algorithm exists for the case of general matrices. However, in many applications the matrices admit certain structural properties that can be used to design faster algorithms. For example, when considering a planar graph, one often works with a Monge matrix A, meaning that the density matrix A^◻ has non-negative entries, that is, A^◻_{i,j} := A_{i+1,j} + A_{i,j+1} - A_{i,j} -A_{i+1,j+1} ≥ 0. The min-plus product of two n×n Monge matrices can be computed in 𝒪(n²) time using the famous SMAWK algorithm. In applications such as longest common subsequence, edit distance, and longest increasing subsequence, the matrices are even more structured, as observed by Tiskin [J. Discrete Algorithms, 2008]: they are (or can be converted to) simple unit-Monge matrices, meaning that the density matrix is a permutation matrix and, furthermore, the first column and the last row of the matrix consist of only zeroes. Such matrices admit an implicit representation of size 𝒪(n) and, as shown by Tiskin [SODA 2010 & Algorithmica, 2015], their min-plus product can be computed in 𝒪(nlog n) time. Russo [SPIRE 2010 & Theor. Comput. Sci., 2012] identified a general structural property of matrices that admit such efficient representation and min-plus multiplication algorithms: the core size δ, defined as the number of non-zero entries in the density matrices of the input and output matrices. He provided an adaptive implementation of the SMAWK algorithm that runs in 𝒪((n+δ)log³ n) or 𝒪((n+δ)log² n) time (depending on the representation of the input matrices). In this work, we further investigate the core size as the parameter that enables efficient min-plus matrix multiplication. On the combinatorial side, we provide a (linear) bound on the core size of the product matrix in terms of the core sizes of the input matrices. On the algorithmic side, we generalize Tiskin’s algorithm (but, arguably, with a more elementary analysis) to solve the core-sparse Monge matrix multiplication problem in 𝒪(n+δlog δ) ⊆ 𝒪(n + δ log n) time, matching the complexity for simple unit-Monge matrices. As witnessed by the recent work of Gorbachev and Kociumaka [STOC'25] for edit distance with integer weights, our generalization opens up the possibility of speed-ups for weighted sequence alignment problems. Furthermore, our multiplication algorithm is also capable of producing an efficient data structure for recovering the witness for any given entry of the output matrix. This allows us, for example, to preprocess an integer array of size n in Õ(n) time so that the longest increasing subsequence of any sub-array can be reconstructed in Õ(𝓁) time, where 𝓁 is the length of the reported subsequence. In comparison, Karthik C. S. and Rahul [arXiv, 2024] recently achieved 𝒪(𝓁+n^{1/2}polylog n)-time reporting after 𝒪(n^{3/2}polylog n)-time preprocessing.
Cite as

Paweł Gawrychowski, Egor Gorbachev, and Tomasz Kociumaka. Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 74:1-74:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gawrychowski_et_al:LIPIcs.ESA.2025.74,
  author =	{Gawrychowski, Pawe{\l} and Gorbachev, Egor and Kociumaka, Tomasz},
  title =	{{Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{74:1--74:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.74},
  URN =		{urn:nbn:de:0030-drops-245427},
  doi =		{10.4230/LIPIcs.ESA.2025.74},
  annote =	{Keywords: Min-plus matrix multiplication, Monge matrix, longest increasing subsequence}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.96
Asymptotically Optimal Inapproximability of Maxmin k-Cut Reconfiguration

Authors: Shuichi Hirahara and Naoto Ohsaka

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
k-Coloring Reconfiguration is one of the most well-studied reconfiguration problems, which asks to transform a given proper k-coloring of a graph to another by repeatedly recoloring a single vertex. Its approximate version, Maxmin k-Cut Reconfiguration, is defined as an optimization problem of maximizing the minimum fraction of bichromatic edges during the transformation between (not necessarily proper) k-colorings. In this paper, we demonstrate that the optimal approximation factor of this problem is 1 - Θ(1/k) for every k ≥ 2. Specifically, we prove the PSPACE-hardness of approximating the objective value within a factor of 1 - ε/k for some universal constant ε > 0, whereas we develop a deterministic polynomial-time algorithm that achieves the approximation factor of 1 - 2/k. To prove the hardness result, we propose a new probabilistic verifier that tests a "striped" pattern. Our approximation algorithm is based on a random transformation that passes through a random k-coloring.
Cite as

Shuichi Hirahara and Naoto Ohsaka. Asymptotically Optimal Inapproximability of Maxmin k-Cut Reconfiguration. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 96:1-96:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hirahara_et_al:LIPIcs.ICALP.2025.96,
  author =	{Hirahara, Shuichi and Ohsaka, Naoto},
  title =	{{Asymptotically Optimal Inapproximability of Maxmin k-Cut Reconfiguration}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{96:1--96:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.96},
  URN =		{urn:nbn:de:0030-drops-234733},
  doi =		{10.4230/LIPIcs.ICALP.2025.96},
  annote =	{Keywords: reconfiguration problems, graph coloring, hardness of approximation}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.6
DULL: A Fast Scalable Detectable Unrolled Lock-Based Linked List

Authors: Ahmed Fahmy and Wojciech Golab

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
Persistent memory (PM) has emerged as a promising technology that enables data structures to preserve their consistent state after recovering from system failures. Detectable data structures have been proposed to detect the response of the last operation of a crashed process. Various lock-free detectable and recoverable concurrent data structures have been developed in the literature. However, designing detectable lock-based structures is challenging due to the need to preserve the correctness properties of the underlying locks, such as mutual exclusion and deadlock-freedom, across failures. Therefore, lock-based detectable and persistent data structures are not as common as lock-free structures. In this work, we introduce DULL: a fast, scalable and Detectable Unrolled Lock-based Linked list. This paper presents the design and implementation of DULL, along with an evaluation of its recoverability and scalability. Experimental Results show that DULL is several-fold faster than the competition in all workloads that involve updates. Moreover, as opposed to some of the previous works, our algorithm is scalable when the multiprocessor is oversubscribed. DULL is a demonstration of the feasibility of using lock-based data structures with detectability in PM environments. We believe that DULL opens up new research directions for designing and analyzing detectable lock-based data structures.
Cite as

Ahmed Fahmy and Wojciech Golab. DULL: A Fast Scalable Detectable Unrolled Lock-Based Linked List. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 6:1-6:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{fahmy_et_al:LIPIcs.OPODIS.2024.6,
  author =	{Fahmy, Ahmed and Golab, Wojciech},
  title =	{{DULL: A Fast Scalable Detectable Unrolled Lock-Based Linked List}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{6:1--6:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.6},
  URN =		{urn:nbn:de:0030-drops-225429},
  doi =		{10.4230/LIPIcs.OPODIS.2024.6},
  annote =	{Keywords: detectability, lock-based, mutual exclusion, linked list, fault-tolerance, persistent memory, concurrency}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.5
RMR-Efficient Detectable Objects for Persistent Memory and Their Applications

Authors: Sahil Dhoked, Ahmed Fahmy, Wojciech Golab, and Neeraj Mittal

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
We describe a novel construction of arbitrary read-modify-write (RMW) primitives in a persistent shared memory model with process failures. Our construction uses blocking synchronization, in the form of recoverable mutual exclusion (RME), and is optimal in terms of the widely studied remote memory reference (RMR) complexity measure. The implemented objects tolerate either system-wide or independent process crashes, depending on the RME lock used, and also provide detectability for resolving the outcome of operations interrupted by failures. We prove that our construction is RMR-optimal using a reduction back to the RME problem. Our proof technique introduces a novel algorithmic style that enables solving challenging synchronization problems using a common execution path for both the system-wide and independent failure models, which previously required separate analyses, and relies only on a suitable implementation of the detectable base objects in each model to achieve RMR efficiency. Experiments demonstrate that our construction outperforms prior wait-free and lock-free algorithms on a multiprocessor with Intel Optane persistent memory.
Cite as

Sahil Dhoked, Ahmed Fahmy, Wojciech Golab, and Neeraj Mittal. RMR-Efficient Detectable Objects for Persistent Memory and Their Applications. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 5:1-5:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dhoked_et_al:LIPIcs.OPODIS.2024.5,
  author =	{Dhoked, Sahil and Fahmy, Ahmed and Golab, Wojciech and Mittal, Neeraj},
  title =	{{RMR-Efficient Detectable Objects for Persistent Memory and Their Applications}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{5:1--5:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.5},
  URN =		{urn:nbn:de:0030-drops-225417},
  doi =		{10.4230/LIPIcs.OPODIS.2024.5},
  annote =	{Keywords: persistent memory, synchronization, recoverability, fault tolerance, detectability, scalability, RMR complexity, theory, mutual exclusion}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2024.53
Brief Announcement: Concurrent Aggregate Queries

Authors: Gal Sela and Erez Petrank

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
Concurrent data structures serve as fundamental building blocks for concurrent computing. Many concurrent counterparts have been designed for basic sequential algorithms; however, one notable omission is a concurrent tree that supports aggregate queries. Aggregate queries essentially compile succinct information about a range of data items. Such queries play an essential role in various applications and are commonly taught in undergraduate data structures courses. In this paper, we formalize a type of aggregate queries that can be efficiently supported by concurrent trees and present a design for implementing these queries on concurrent lock-based trees. We present two algorithms implementing this design, where one optimizes for tree update time, while the other optimizes for aggregate query time.
Cite as

Gal Sela and Erez Petrank. Brief Announcement: Concurrent Aggregate Queries. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 53:1-53:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{sela_et_al:LIPIcs.DISC.2024.53,
  author =	{Sela, Gal and Petrank, Erez},
  title =	{{Brief Announcement: Concurrent Aggregate Queries}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{53:1--53:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.53},
  URN =		{urn:nbn:de:0030-drops-212819},
  doi =		{10.4230/LIPIcs.DISC.2024.53},
  annote =	{Keywords: Concurrent Algorithms, Concurrent Data Structures, Aggregate queries, Range queries, Binary Search Tree, Linearizability}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2022.5
EEMARQ: Efficient Lock-Free Range Queries with Memory Reclamation

Authors: Gali Sheffi, Pedro Ramalhete, and Erez Petrank

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
Multi-Version Concurrency Control (MVCC) is a common mechanism for achieving linearizable range queries in database systems and concurrent data-structures. The core idea is to keep previous versions of nodes to serve range queries, while still providing atomic reads and updates. Existing concurrent data-structure implementations, that support linearizable range queries, are either slow, use locks, or rely on blocking reclamation schemes. We present EEMARQ, the first scheme that uses MVCC with lock-free memory reclamation to obtain a fully lock-free data-structure supporting linearizable inserts, deletes, contains, and range queries. Evaluation shows that EEMARQ outperforms existing solutions across most workloads, with lower space overhead and while providing full lock freedom.
Cite as

Gali Sheffi, Pedro Ramalhete, and Erez Petrank. EEMARQ: Efficient Lock-Free Range Queries with Memory Reclamation. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 5:1-5:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{sheffi_et_al:LIPIcs.OPODIS.2022.5,
  author =	{Sheffi, Gali and Ramalhete, Pedro and Petrank, Erez},
  title =	{{EEMARQ: Efficient Lock-Free Range Queries with Memory Reclamation}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{5:1--5:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.5},
  URN =		{urn:nbn:de:0030-drops-176253},
  doi =		{10.4230/LIPIcs.OPODIS.2022.5},
  annote =	{Keywords: safe memory reclamation, lock-freedom, snapshot, concurrency, range query}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.35
VBR: Version Based Reclamation

Authors: Gali Sheffi, Maurice Herlihy, and Erez Petrank

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
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.
Cite as

Gali Sheffi, Maurice Herlihy, and Erez Petrank. VBR: Version Based Reclamation. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 35:1-35:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{sheffi_et_al:LIPIcs.DISC.2021.35,
  author =	{Sheffi, Gali and Herlihy, Maurice and Petrank, Erez},
  title =	{{VBR: Version Based Reclamation}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{35:1--35:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.35},
  URN =		{urn:nbn:de:0030-drops-148374},
  doi =		{10.4230/LIPIcs.DISC.2021.35},
  annote =	{Keywords: Safe memory reclamation, concurrency, linearizability, lock-freedom}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2017.10
The Teleportation Design Pattern for Hardware Transactional Memory

Authors: Nachshon Cohen, Maurice Herlihy, Erez Petrank, and Elias Wald

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
We identify a design pattern for concurrent data structures, called teleportation, that uses best- effort hardware transactional memory to speed up certain kinds of legacy concurrent data struc- tures. Teleportation unifies and explains several existing data structure designs, and it serves as the basis for novel approaches to reducing the memory traffic associated with fine-grained locking, and with hazard pointer management for memory reclamation.
Cite as

Nachshon Cohen, Maurice Herlihy, Erez Petrank, and Elias Wald. The Teleportation Design Pattern for Hardware Transactional Memory. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.OPODIS.2017.10,
  author =	{Cohen, Nachshon and Herlihy, Maurice and Petrank, Erez and Wald, Elias},
  title =	{{The Teleportation Design Pattern for Hardware Transactional Memory}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.10},
  URN =		{urn:nbn:de:0030-drops-86306},
  doi =		{10.4230/LIPIcs.OPODIS.2017.10},
  annote =	{Keywords: Hardware transactional memory, concurrent data structures}
}
Document
DOI: 10.4230/DagRep.7.11.1
New Challenges in Parallelism (Dagstuhl Seminar 17451)

Authors: Annette Bieniusa, Hans-J. Boehm, Maurice Herlihy, and Erez Petrank

Published in: Dagstuhl Reports, Volume 7, Issue 11 (2018)

Abstract
A continuing goal of current multiprocessor software design is to improve the performance and reliability of parallel algorithms. Parallel programming has traditionally been attacked from widely different angles by different groups of people: Hardware designers designing instruction sets, programming language designers designing languages and library interfaces, and theoreticians developing models of parallel computation. Unsurprisingly, this has not always led to consistent results. Newly developing areas show every sign of leading to similar divergence. This Dagstuhl Seminar will bring together researchers and practitioners from all three areas to discuss and reconcile thoughts on these challenges.
Cite as

Annette Bieniusa, Hans-J. Boehm, Maurice Herlihy, and Erez Petrank. New Challenges in Parallelism (Dagstuhl Seminar 17451). In Dagstuhl Reports, Volume 7, Issue 11, pp. 1-27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{bieniusa_et_al:DagRep.7.11.1,
  author =	{Bieniusa, Annette and Boehm, Hans-J. and Herlihy, Maurice and Petrank, Erez},
  title =	{{New Challenges in Parallelism (Dagstuhl Seminar 17451)}},
  pages =	{1--27},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2018},
  volume =	{7},
  number =	{11},
  editor =	{Bieniusa, Annette and Boehm, Hans-J. and Herlihy, Maurice and Petrank, Erez},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.11.1},
  URN =		{urn:nbn:de:0030-drops-86681},
  doi =		{10.4230/DagRep.7.11.1},
  annote =	{Keywords: concurrency, memory models, non-volatile memory}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2017.50
Brief Announcement: A Persistent Lock-Free Queue for Non-Volatile Memory

Authors: Michal Friedman, Maurice Herlihy, Virendra Marathe, and Erez Petrank

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
Non-volatile memory is expected to coexist with (or even displace) volatile DRAM for main memory in upcoming architectures. As a result, there is increasing interest in the problem of designing and specifying durable data structures that can recover from system crashes. Data-structures may be designed to satisfy stricter or weaker durability guarantees to provide a balance between the strength of the provided guarantees and performance overhead. This paper proposes three novel implementations of a concurrent lock-free queue. These implementations illustrate the algorithmic challenges in building persistent lock-free data structures with different levels of durability guarantees. We believe that by presenting these challenges, along with the proposed algorithmic designs, and the possible levels of durability guarantees, we can shed light on avenues for building a wide variety of durable data structures. We implemented the various designs and evaluate their performance overhead compared to a simple queue design for standard (volatile) memory.
Cite as

Michal Friedman, Maurice Herlihy, Virendra Marathe, and Erez Petrank. Brief Announcement: A Persistent Lock-Free Queue for Non-Volatile Memory. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 50:1-50:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{friedman_et_al:LIPIcs.DISC.2017.50,
  author =	{Friedman, Michal and Herlihy, Maurice and Marathe, Virendra and Petrank, Erez},
  title =	{{Brief Announcement: A Persistent Lock-Free Queue for Non-Volatile Memory}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{50:1--50:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.50},
  URN =		{urn:nbn:de:0030-drops-79689},
  doi =		{10.4230/LIPIcs.DISC.2017.50},
  annote =	{Keywords: Non-volatile Memory, Concurrent Data Structures, Non-blocking, Lock-free}
}
  • Refine by Type
  • 13 Document/PDF
  • 7 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 6 2025
  • 1 2024
  • 1 2023
  • 1 2021
  • Show More...

  • Refine by Author
  • 6 Petrank, Erez
  • 4 Herlihy, Maurice
  • 3 Fatourou, Panagiota
  • 2 Fahmy, Ahmed
  • 2 Golab, Wojciech
  • Show More...

  • Refine by Series/Journal
  • 12 LIPIcs
  • 1 DagRep

  • Refine by Classification
  • 4 Theory of computation → Concurrent algorithms
  • 3 Theory of computation → Data structures design and analysis
  • 1 Computer systems organization → Reliability
  • 1 Computing methodologies → Concurrent algorithms
  • 1 Computing methodologies → Shared memory algorithms
  • Show More...

  • Refine by Keyword
  • 4 concurrency
  • 3 Concurrent Data Structures
  • 3 lock-freedom
  • 2 detectability
  • 2 mutual exclusion
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact