3 Search Results for "Rukundo, Adones"

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.ESA.2025.85
A Simple yet Exact Analysis of the MultiQueue

Authors: Stefan Walzer and Marvin Williams

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

Abstract
The MultiQueue is a relaxed concurrent priority queue consisting of n internal priority queues, where an insertion uses a random queue and a deletion considers two random queues and deletes the minimum from the one with the smaller minimum. The rank error of the deletion is the number of smaller elements in the MultiQueue. Alistarh et al. [Alistarh et al., 2017] have demonstrated in a sophisticated potential argument that the expected rank error remains bounded by 𝒪(n) over long sequences of deletions. In this paper we present a simpler analysis by identifying the stable distribution of an underlying Markov chain and with it the long-term distribution of the rank error exactly. Simple calculations then reveal the expected long-term rank error to be (5/6)n-1+1/(6n). Our arguments generalize to deletion schemes where the probability to delete from a given queue depends only on the rank of the queue. Specifically, this includes deleting from the best of c randomly selected queues for any c > 1.
Cite as

Stefan Walzer and Marvin Williams. A Simple yet Exact Analysis of the MultiQueue. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 85:1-85:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{walzer_et_al:LIPIcs.ESA.2025.85,
  author =	{Walzer, Stefan and Williams, Marvin},
  title =	{{A Simple yet Exact Analysis of the MultiQueue}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{85:1--85:14},
  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.85},
  URN =		{urn:nbn:de:0030-drops-245533},
  doi =		{10.4230/LIPIcs.ESA.2025.85},
  annote =	{Keywords: MultiQueue, concurrent data structure, stochastic process, Markov chain}
}
Document
DOI: 10.4230/LIPIcs.DISC.2019.31
Monotonically Relaxing Concurrent Data-Structure Semantics for Increasing Performance: An Efficient 2D Design Framework

Authors: Adones Rukundo, Aras Atalar, and Philippas Tsigas

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

Abstract
There has been a significant amount of work in the literature proposing semantic relaxation of concurrent data structures for improving scalability and performance. By relaxing the semantics of a data structure, a bigger design space, that allows weaker synchronization and more useful parallelism, is unveiled. Investigating new data structure designs, capable of trading semantics for achieving better performance in a monotonic way, is a major challenge in the area. We algorithmically address this challenge in this paper. We present an efficient, lock-free, concurrent data structure design framework for out-of-order semantic relaxation. We introduce a new two dimensional algorithmic design, that uses multiple instances of a given data structure. The first dimension of our design is the number of data structure instances operations are spread to, in order to benefit from parallelism through disjoint memory access; the second dimension is the number of consecutive operations that try to use the same data structure instance in order to benefit from data locality. Our design can flexibly explore this two-dimensional space to achieve the property of monotonically relaxing concurrent data structure semantics for better performance within a tight deterministic relaxation bound, as we prove in the paper. We show how our framework can instantiate lock-free out-of-order queues, stacks, counters and dequeues. We provide implementations of these relaxed data structures and evaluate their performance and behaviour on two parallel architectures. Experimental evaluation shows that our two-dimensional design significantly outperforms the respected previous proposed designs with respect to scalability and performance. Moreover, our design increases performance monotonically as relaxation increases.
Cite as

Adones Rukundo, Aras Atalar, and Philippas Tsigas. Monotonically Relaxing Concurrent Data-Structure Semantics for Increasing Performance: An Efficient 2D Design Framework. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 31:1-31:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{rukundo_et_al:LIPIcs.DISC.2019.31,
  author =	{Rukundo, Adones and Atalar, Aras and Tsigas, Philippas},
  title =	{{Monotonically Relaxing Concurrent Data-Structure Semantics for Increasing Performance: An Efficient 2D Design Framework}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{31:1--31:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.31},
  URN =		{urn:nbn:de:0030-drops-113382},
  doi =		{10.4230/LIPIcs.DISC.2019.31},
  annote =	{Keywords: Lock Free, Concurrency, Semantics Relaxation, Data Structures}
}
  • Refine by Type
  • 3 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 1 2019

  • Refine by Author
  • 1 Atalar, Aras
  • 1 Fatourou, Panagiota
  • 1 Rukundo, Adones
  • 1 Ruppert, Eric
  • 1 Tsigas, Philippas
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 3 Theory of computation → Data structures design and analysis
  • 2 Theory of computation → Concurrent algorithms
  • 1 Computing methodologies → Concurrent algorithms
  • 1 Mathematics of computing → Stochastic processes
  • 1 Theory of computation → Concurrency
  • Show More...

  • Refine by Keyword
  • 1 Concurrency
  • 1 Data Structures
  • 1 Lock Free
  • 1 Markov chain
  • 1 MultiQueue
  • 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