Search Results

Documents authored by Fatourou, Panagiota

Document
DOI: 10.4230/LIPIcs.DISC.2024.23
Lock-Free Augmented Trees

Authors: Panagiota Fatourou and Eric Ruppert

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

Abstract
Augmenting an existing sequential data structure with extra information to support greater functionality is a widely used technique. For example, search trees are augmented to build sequential data structures like order-statistic trees, interval trees, tango trees, link/cut trees and many others. We study how to design concurrent augmented tree data structures. We present a new, general technique that can augment a lock-free tree to add any new fields to each tree node, provided the new fields' values can be computed from information in the node and its children. This enables the design of lock-free, linearizable analogues of a wide variety of classical augmented data structures. As a first example, we give a wait-free trie that stores a set S of elements drawn from {0,…,N-1} and supports linearizable order-statistic queries such as finding the kth smallest element of S. Updates and queries take O(log N) steps. We also apply our technique to a lock-free binary search tree (BST), where changes to the structure of the tree make the linearization argument more challenging. Our augmented BST supports order statistic queries in O(h) steps on a tree of height h. The augmentation does not affect the asymptotic step complexity of the updates. As an added bonus, our technique supports arbitrary multi-point queries (such as range queries) with the same step complexity as they would have in the corresponding sequential data structure. For both our trie and BST, we give an alternative augmentation to improve searches and order-statistic queries to run in O(log |S|) steps (at the cost of increasing step complexity of updates by a factor of O(log|S|)).
Cite as

Panagiota Fatourou and Eric Ruppert. Lock-Free Augmented Trees. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 23:1-23:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{fatourou_et_al:LIPIcs.DISC.2024.23,
  author =	{Fatourou, Panagiota and Ruppert, Eric},
  title =	{{Lock-Free Augmented Trees}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{23:1--23:24},
  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.23},
  URN =		{urn:nbn:de:0030-drops-212499},
  doi =		{10.4230/LIPIcs.DISC.2024.23},
  annote =	{Keywords: shared-memory, data structure, tree, binary search tree, augmentation, linearizable, lock-free, order statistic, snapshot}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.OPODIS.2022.2
Recoverable Computing (Invited Talk)

Authors: Panagiota Fatourou

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

Abstract
Non-Volatile Memory (NVM) is an emerging memory technology which aims to address the high computational demands of modern applications and support recovery from crashes. Recovery ensures that after a crash every executed operation is able to recover and return a correct response. This talk will shed light on different aspects of the question "How does concurrent computing change in systems with NVM and what will the impact of persistent memory be on the way we compute?". Specifically, this talk addresses the following four main challenges in NVM computing. - Challenge 1: How to appropriately model and abstract fundamental aspects of NVM computing? The talk will provide an overview of the theoretical framework for NVM computing, including a discussion of correctness conditions, progress guarantees, failure types, etc. - Challenge 2: How to compute in a recoverable way at no significant cost? The talk will summarize state-of-the-art generic approaches for deriving recoverable synchronization algorithms, as well as recoverable implementations of many widely-used concurrent data structures on top of them. The collection of data structures includes fundamental structures, such as stacks and queues, but also more complex structures that implement sets, such as linked-lists and trees. - Challenge 3: How to analyze the cost of recoverable algorithms? The talk will present a way of analyzing the cost of persistence instructions, not by simply counting them but by separating them into categories based on the impact they have on the performance. This analysis reveals that understanding the actual persistence cost of an algorithm in machines with NVM, is more complicated than previously thought, and requires a thorough evaluation, since the performance impact of different persistence instructions may greatly vary. - Challenge 4: When is Recoverable Consensus Harder Than Consensus? The talk will briefly discuss the ability of different shared object types to solve recoverable consensus using NVM when processes crash and recover, and it will compare the difficulty of solving recoverable consensus to the difficulty of solving the standard consensus problem in a system with halting failures. For each of the above challenges, the talk will present main results, provide some of the details of the best-performing techniques, and discuss open problems and directions for further research. Some of the results that will be discussed in detail have appeared in [Attiya et al., 2022; Delporte-Gallet et al., 2022; Fatourou et al., 2022].
Cite as

Panagiota Fatourou. Recoverable Computing (Invited Talk). In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 2:1-2:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{fatourou:LIPIcs.OPODIS.2022.2,
  author =	{Fatourou, Panagiota},
  title =	{{Recoverable Computing}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{2:1--2:2},
  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.2},
  URN =		{urn:nbn:de:0030-drops-176221},
  doi =		{10.4230/LIPIcs.OPODIS.2022.2},
  annote =	{Keywords: non-volatile memory, persistence, detectability, durability, recoverable algorithms, recoverable data structures, persistent objects, stacks, queues, heaps, synchronization, universal constructions, software combining, lock-freedom, wait-freedom, persistence cost analysis}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.12
Space and Time Bounded Multiversion Garbage Collection

Authors: Naama Ben-David, Guy E. Blelloch, Panagiota Fatourou, Eric Ruppert, Yihan Sun, and Yuanhao Wei

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

Abstract
We present a general technique for garbage collecting old versions for multiversion concurrency control that simultaneously achieves good time and space complexity. Our technique takes only O(1) time on average to reclaim each version and maintains only a constant factor more versions than needed (plus an additive term). It is designed for multiversion schemes using version lists, which are the most common. Our approach uses two components that are of independent interest. First, we define a novel range-tracking data structure which stores a set of old versions and efficiently finds those that are no longer needed. We provide a wait-free implementation in which all operations take amortized constant time. Second, we represent version lists using a new lock-free doubly-linked list algorithm that supports efficient (amortized constant time) removals given a pointer to any node in the list. These two components naturally fit together to solve the multiversion garbage collection problem - the range-tracker identifies which versions to remove and our list algorithm can then be used to remove them from their version lists. We apply our garbage collection technique to generate end-to-end time and space bounds for the multiversioning system of Wei et al. (PPoPP 2021).
Cite as

Naama Ben-David, Guy E. Blelloch, Panagiota Fatourou, Eric Ruppert, Yihan Sun, and Yuanhao Wei. Space and Time Bounded Multiversion Garbage Collection. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bendavid_et_al:LIPIcs.DISC.2021.12,
  author =	{Ben-David, Naama and Blelloch, Guy E. and Fatourou, Panagiota and Ruppert, Eric and Sun, Yihan and Wei, Yuanhao},
  title =	{{Space and Time Bounded Multiversion Garbage Collection}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{12:1--12:20},
  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.12},
  URN =		{urn:nbn:de:0030-drops-148143},
  doi =		{10.4230/LIPIcs.DISC.2021.12},
  annote =	{Keywords: Lock-free, data structures, memory management, snapshot, version lists}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2021.56
Brief Announcement: Persistent Software Combining

Authors: Panagiota Fatourou, Nikolaos D. Kallimanis, and Eleftherios Kosmas

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

Abstract
We study the performance power of software combining in designing recoverable algorithms and data structures. We present two recoverable synchronization protocols, one blocking and another wait-free, which illustrate how to use software combining to achieve both low persistence and synchronization cost. Our experiments show that these protocols outperform by far state-of-the-art recoverable universal constructions and transactional memory systems. We built recoverable queues and stacks, based on these protocols, that exhibit much better performance than previous such implementations.
Cite as

Panagiota Fatourou, Nikolaos D. Kallimanis, and Eleftherios Kosmas. Brief Announcement: Persistent Software Combining. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 56:1-56:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{fatourou_et_al:LIPIcs.DISC.2021.56,
  author =	{Fatourou, Panagiota and Kallimanis, Nikolaos D. and Kosmas, Eleftherios},
  title =	{{Brief Announcement: Persistent Software Combining}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{56:1--56:4},
  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.56},
  URN =		{urn:nbn:de:0030-drops-148580},
  doi =		{10.4230/LIPIcs.DISC.2021.56},
  annote =	{Keywords: Persistent objects, recoverable algorithms, durability, synchronization protocols, software combining, universal constructions, wait-freedom, stacks, queues}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.18
An Efficient Universal Construction for Large Objects

Authors: Panagiota Fatourou, Nikolaos D. Kallimanis, and Eleni Kanellou

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
This paper presents L-UC, a universal construction that efficiently implements dynamic objects of large state in a wait-free manner. The step complexity of L-UC is O(n+kw), where n is the number of processes, k is the interval contention (i.e., the maximum number of active processes during the execution interval of an operation), and w is the worst-case time complexity to perform an operation on the sequential implementation of the simulated object. L-UC efficiently implements objects whose size can change dynamically. It improves upon previous universal constructions either by efficiently handling objects whose state is large and can change dynamically, or by achieving better step complexity.
Cite as

Panagiota Fatourou, Nikolaos D. Kallimanis, and Eleni Kanellou. An Efficient Universal Construction for Large Objects. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{fatourou_et_al:LIPIcs.OPODIS.2019.18,
  author =	{Fatourou, Panagiota and Kallimanis, Nikolaos D. and Kanellou, Eleni},
  title =	{{An Efficient Universal Construction for Large Objects}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{18:1--18:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.18},
  URN =		{urn:nbn:de:0030-drops-118049},
  doi =		{10.4230/LIPIcs.OPODIS.2019.18},
  annote =	{Keywords: universal construction, concurrent object, shared memory, simulation, wait-freedom, large object}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2017.8
Lock Oscillation: Boosting the Performance of Concurrent Data Structures

Authors: Panagiota Fatourou and Nikolaos D. Kallimanis

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

Abstract
In combining-based synchronization, two main parameters that affect performance are the com- bining degree of the synchronization algorithm, i.e. the average number of requests that each com- biner serves, and the number of expensive synchronization primitives (like CAS, Swap, etc.) that it performs. The value of the first parameter must be high, whereas the second must be kept low. In this paper, we present Osci, a new combining technique that shows remarkable perform- ance when paired with cheap context switching. We experimentally show that Osci significantly outperforms all previous combining algorithms. Specifically, the throughput of Osci is higher than that of previously presented combining techniques by more than an order of magnitude. Notably, Osci’s throughput is much closer to the ideal than all previous algorithms, while keep- ing the average latency in serving each request low. We evaluated the performance of Osci in two different multiprocessor architectures, namely AMD and Intel. Based on Osci, we implement and experimentally evaluate implementations of concurrent queues and stacks. These implementations outperform by far all current state-of-the-art concur- rent queue and stack implementations. Although the current version of Osci has been evaluated in an environment supporting user-level threads, it would run correctly on any threading library, preemptive or not (including kernel threads).
Cite as

Panagiota Fatourou and Nikolaos D. Kallimanis. Lock Oscillation: Boosting the Performance of Concurrent Data Structures. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{fatourou_et_al:LIPIcs.OPODIS.2017.8,
  author =	{Fatourou, Panagiota and Kallimanis, Nikolaos D.},
  title =	{{Lock Oscillation: Boosting the Performance of Concurrent Data Structures}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{8:1--8:17},
  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.8},
  URN =		{urn:nbn:de:0030-drops-86282},
  doi =		{10.4230/LIPIcs.OPODIS.2017.8},
  annote =	{Keywords: Synchronization, concurrent data structures, combining}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.OPODIS.2016
LIPIcs, Volume 70, OPODIS'16, Complete Volume

Authors: Panagiota Fatourou, Ernesto Jiménez, and Fernando Pedone

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
LIPIcs, Volume 70, OPODIS'16, Complete Volume
Cite as

20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Proceedings{fatourou_et_al:LIPIcs.OPODIS.2016,
  title =	{{LIPIcs, Volume 70, OPODIS'16, Complete Volume}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016},
  URN =		{urn:nbn:de:0030-drops-71111},
  doi =		{10.4230/LIPIcs.OPODIS.2016},
  annote =	{Keywords: Distributed Systems, Performance of Systems, Concurrent Programming, Data Structures, Modes of Computation}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.OPODIS.2016.0
Front Matter, Table of Contents, Preface, Committees, List of Authors

Authors: Panagiota Fatourou, Ernesto Jiménez, and Fernando Pedone

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
Front Matter, Table of Contents, Preface, Committees, List of Authors
Cite as

20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{fatourou_et_al:LIPIcs.OPODIS.2016.0,
  author =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  title =	{{Front Matter, Table of Contents, Preface, Committees, List of Authors}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{0:i--0:xviii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.0},
  URN =		{urn:nbn:de:0030-drops-70699},
  doi =		{10.4230/LIPIcs.OPODIS.2016.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Committees, List of Authors}
}
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