2 Search Results for "Kanellou, Eleni"

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-dev.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.2015.27
Wait-Free Concurrent Graph Objects with Dynamic Traversals

Authors: Nikolaos D. Kallimanis and Eleni Kanellou

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract
Graphs are versatile data structures that allow the implementation of a variety of applications, such as computer-aided design and manufacturing, video gaming, or scientific simulations. However, although data structures such as queues, stacks, and trees have been widely studied and implemented in the concurrent context, multi-process applications that rely on graphs still largely use a sequential implementation where accesses are synchronized through the use of global locks or partitioning, thus imposing serious performance bottlenecks. In this paper we introduce an innovative concurrent graph model that provides addition and removal of any edge of the graph, as well as atomic traversals of a part (or the entirety) of the graph. We further present Dense, a concurrent graph implementation that aims at mitigating the two aforementioned implementation drawbacks. Dense achieves wait-freedom by relying on helping and provides the inbuilt capability of performing a partial snapshot on a dynamically determined subset of the graph.
Cite as

Nikolaos D. Kallimanis and Eleni Kanellou. Wait-Free Concurrent Graph Objects with Dynamic Traversals. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kallimanis_et_al:LIPIcs.OPODIS.2015.27,
  author =	{Kallimanis, Nikolaos D. and Kanellou, Eleni},
  title =	{{Wait-Free Concurrent Graph Objects with Dynamic Traversals}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{27:1--27:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.27},
  URN =		{urn:nbn:de:0030-drops-66164},
  doi =		{10.4230/LIPIcs.OPODIS.2015.27},
  annote =	{Keywords: graph, shared memory, concurrent data structure, snapshot}
}
  • Refine by Author
  • 2 Kallimanis, Nikolaos D.
  • 2 Kanellou, Eleni
  • 1 Fatourou, Panagiota

  • Refine by Classification
  • 1 Computing methodologies → Concurrent algorithms
  • 1 Computing methodologies → Concurrent computing methodologies
  • 1 Computing methodologies → Shared memory algorithms
  • 1 Theory of computation → Concurrent algorithms
  • 1 Theory of computation → Shared memory algorithms

  • Refine by Keyword
  • 2 shared memory
  • 1 concurrent data structure
  • 1 concurrent object
  • 1 graph
  • 1 large object
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2016
  • 1 2020

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