Search Results

Documents authored by Sela, Gal

Document
DOI: 10.4230/LIPIcs.DISC.2025.29
Strong Linearizability Without Compare&Swap: The Case of Bags

Authors: Faith Ellen and Gal Sela

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

Abstract
Because strongly-linearizable objects provide stronger guarantees than linearizability, they serve as valuable building blocks for the design of concurrent data structures. Yet, many objects that have linearizable implementations from base objects weaker than compare&swap objects do not have strongly-linearizable implementations from the same base objects. We focus on one such object: the bag, a multiset from which processes can take unspecified elements. We present the first lock-free, strongly-linearizable implementation of a bag from interfering objects (specifically, registers and test&set objects). This may be surprising, since there are provably no such implementations of stacks or queues. Since a bag can contain arbitrarily many elements, an unbounded amount of space must be used to implement it. Hence, it makes sense to also consider a bag with a bound on its capacity. However, like stacks and queues, a bag with capacity b shared by more than 2b processes has no lock-free, strongly-linearizable implementation from interfering objects. If we further restrict a bounded bag so that only one process can insert into it, we are able to obtain a lock-free, strongly-linearizable implementation from O(b+n) interfering objects, where n is the number of processes. Our goal is to understand the circumstances under which strongly-linearizable implementations of bags exist and, more generally, to understand the power of interfering objects.
Cite as

Faith Ellen and Gal Sela. Strong Linearizability Without Compare&Swap: The Case of Bags. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 29:1-29:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ellen_et_al:LIPIcs.DISC.2025.29,
  author =	{Ellen, Faith and Sela, Gal},
  title =	{{Strong Linearizability Without Compare\&Swap: The Case of Bags}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{29:1--29:19},
  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.29},
  URN =		{urn:nbn:de:0030-drops-248464},
  doi =		{10.4230/LIPIcs.DISC.2025.29},
  annote =	{Keywords: Strong-Linearizability, Bag, Concurrent Data Structures, Wait-Freedom, Lock-Freedom}
}
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}
}
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact