3 Search Results for "Aksenov, Vitaly"

Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2023.35
Brief Announcement: BatchBoost: Universal Batching for Concurrent Data Structures

Authors: Vitaly Aksenov, Michael Anoprenko, Alexander Fedorov, and Michael Spear

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
Batching is a technique that stores multiple keys/values in each node of a data structure. In sequential search data structures, batching reduces latency by reducing the number of cache misses and shortening the chain of pointers to dereference. Applying batching to concurrent data structures is challenging, because it is difficult to maintain the search property and keep contention low in the presence of batching. In this paper, we present a general methodology for leveraging batching in concurrent search data structures, called BatchBoost. BatchBoost builds a search data structure from distinct "data" and "index" layers. The data layer’s purpose is to store a batch of key/value pairs in each of its nodes. The index layer uses an unmodified concurrent search data structure to route operations to a position in the data layer that is "close" to where the corresponding key should exist. The requirements on the index and data layers are low: with minimal effort, we were able to compose three highly scalable concurrent search data structures based on three original data structures as the index layers with a batched version of the Lazy List as the data layer. The resulting BatchBoost data structures provide significant performance improvements over their original counterparts.
Cite as

Vitaly Aksenov, Michael Anoprenko, Alexander Fedorov, and Michael Spear. Brief Announcement: BatchBoost: Universal Batching for Concurrent Data Structures. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 35:1-35:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{aksenov_et_al:LIPIcs.DISC.2023.35,
  author =	{Aksenov, Vitaly and Anoprenko, Michael and Fedorov, Alexander and Spear, Michael},
  title =	{{Brief Announcement: BatchBoost: Universal Batching for Concurrent Data Structures}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{35:1--35:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.35},
  URN =		{urn:nbn:de:0030-drops-191612},
  doi =		{10.4230/LIPIcs.DISC.2023.35},
  annote =	{Keywords: Concurrency, Synchronization, Locality}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.3
The Splay-List: A Distribution-Adaptive Concurrent Skip-List

Authors: Vitaly Aksenov, Dan Alistarh, Alexandra Drozdova, and Amirkeivan Mohtashami

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
The design and implementation of efficient concurrent data structures has seen significant attention. However, most of this work has focused on concurrent data structures providing good worst-case guarantees. In real workloads, objects are often accessed at different rates, since access distributions may be non-uniform. Efficient distribution-adaptive data structures are known in the sequential case, e.g. the splay-trees; however, they often are hard to translate efficiently in the concurrent case. In this paper, we investigate distribution-adaptive concurrent data structures, and propose a new design called the splay-list. At a high level, the splay-list is similar to a standard skip-list, with the key distinction that the height of each element adapts dynamically to its access rate: popular elements "move up," whereas rarely-accessed elements decrease in height. We show that the splay-list provides order-optimal amortized complexity bounds for a subset of operations, while being amenable to efficient concurrent implementation. Experimental results show that the splay-list can leverage distribution-adaptivity to improve on the performance of classic concurrent designs, and can outperform the only previously-known distribution-adaptive design in certain settings.
Cite as

Vitaly Aksenov, Dan Alistarh, Alexandra Drozdova, and Amirkeivan Mohtashami. The Splay-List: A Distribution-Adaptive Concurrent Skip-List. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 3:1-3:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{aksenov_et_al:LIPIcs.DISC.2020.3,
  author =	{Aksenov, Vitaly and Alistarh, Dan and Drozdova, Alexandra and Mohtashami, Amirkeivan},
  title =	{{The Splay-List: A Distribution-Adaptive Concurrent Skip-List}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{3:1--3:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.3},
  URN =		{urn:nbn:de:0030-drops-130818},
  doi =		{10.4230/LIPIcs.DISC.2020.3},
  annote =	{Keywords: Data structures, self-adjusting, concurrency}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2018.11
Parallel Combining: Benefits of Explicit Synchronization

Authors: Vitaly Aksenov, Petr Kuznetsov, and Anatoly Shalyto

Published in: LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)

Abstract
A parallel batched data structure is designed to process synchronized batches of operations on the data structure using a parallel program. In this paper, we propose parallel combining, a technique that implements a concurrent data structure from a parallel batched one. The idea is that we explicitly synchronize concurrent operations into batches: one of the processes becomes a combiner which collects concurrent requests and initiates a parallel batched algorithm involving the owners (clients) of the collected requests. Intuitively, the cost of synchronizing the concurrent calls can be compensated by running the parallel batched algorithm. We validate the intuition via two applications. First, we use parallel combining to design a concurrent data structure optimized for read-dominated workloads, taking a dynamic graph data structure as an example. Second, we use a novel parallel batched priority queue to build a concurrent one. In both cases, we obtain performance gains with respect to the state-of-the-art algorithms.
Cite as

Vitaly Aksenov, Petr Kuznetsov, and Anatoly Shalyto. Parallel Combining: Benefits of Explicit Synchronization. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{aksenov_et_al:LIPIcs.OPODIS.2018.11,
  author =	{Aksenov, Vitaly and Kuznetsov, Petr and Shalyto, Anatoly},
  title =	{{Parallel Combining: Benefits of Explicit Synchronization}},
  booktitle =	{22nd International Conference on Principles of Distributed Systems (OPODIS 2018)},
  pages =	{11:1--11:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{125},
  editor =	{Cao, Jiannong and Ellen, Faith and Rodrigues, Luis and Ferreira, Bernardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.11},
  URN =		{urn:nbn:de:0030-drops-100713},
  doi =		{10.4230/LIPIcs.OPODIS.2018.11},
  annote =	{Keywords: concurrent data structure, parallel batched data structure, combining}
}
  • Refine by Author
  • 3 Aksenov, Vitaly
  • 1 Alistarh, Dan
  • 1 Anoprenko, Michael
  • 1 Drozdova, Alexandra
  • 1 Fedorov, Alexander
  • Show More...

  • Refine by Classification
  • 1 Computing methodologies → Concurrent algorithms
  • 1 Computing methodologies → Concurrent computing methodologies
  • 1 Computing methodologies → Parallel computing methodologies
  • 1 Theory of computation → Concurrent algorithms
  • 1 Theory of computation → Data structures design and analysis
  • Show More...

  • Refine by Keyword
  • 1 Concurrency
  • 1 Data structures
  • 1 Locality
  • 1 Synchronization
  • 1 combining
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2019
  • 1 2020
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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