License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2015.27
URN: urn:nbn:de:0030-drops-66164
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6616/
Go to the corresponding LIPIcs Volume Portal

Kallimanis, Nikolaos D. ; Kanellou, Eleni

Wait-Free Concurrent Graph Objects with Dynamic Traversals

pdf-format:
LIPIcs-OPODIS-2015-27.pdf (0.5 MB)

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.

BibTeX - Entry

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

Keywords: graph, shared memory, concurrent data structure, snapshot
Collection: 19th International Conference on Principles of Distributed Systems (OPODIS 2015)
Issue Date: 2016
Date of publication: 13.10.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI