Search Results

Documents authored by Sela, Gal

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.DISC.2023.9
The FIDS Theorems: Tensions Between Multinode and Multicore Performance in Transactional Systems

Authors: Naama Ben-David, Gal Sela, and Adriana Szekeres

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

Abstract
Traditionally, distributed and parallel transactional systems have been studied in isolation, as they targeted different applications and experienced different bottlenecks. However, modern high-bandwidth networks have made the study of systems that are both distributed (i.e., employ multiple nodes) and parallel (i.e., employ multiple cores per node) necessary to truly make use of the available hardware. In this paper, we study the performance of these combined systems and show that there are inherent tradeoffs between a system’s ability to have fast and robust distributed communication and its ability to scale to multiple cores. More precisely, we formalize the notions of a fast deciding path of communication to commit transactions quickly in good executions, and seamless fault tolerance that allows systems to remain robust to server failures. We then show that there is an inherent tension between these two natural distributed properties and well-known multicore scalability properties in transactional systems. Finally, we show positive results; it is possible to construct a parallel distributed transactional system if any one of the properties we study is removed.
Cite as

Naama Ben-David, Gal Sela, and Adriana Szekeres. The FIDS Theorems: Tensions Between Multinode and Multicore Performance in Transactional Systems. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 9:1-9:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bendavid_et_al:LIPIcs.DISC.2023.9,
  author =	{Ben-David, Naama and Sela, Gal and Szekeres, Adriana},
  title =	{{The FIDS Theorems: Tensions Between Multinode and Multicore Performance in Transactional Systems}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{9:1--9:24},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.9},
  URN =		{urn:nbn:de:0030-drops-191355},
  doi =		{10.4230/LIPIcs.DISC.2023.9},
  annote =	{Keywords: transactions, distributed systems, parallel systems, impossibility results}
}
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 About DROPS Imprint Privacy Contact