1 Search Results for "Shafiei, Niloufar"

Document
DOI: 10.4230/LIPIcs.OPODIS.2015.35
Non-Blocking Doubly-Linked Lists with Good Amortized Complexity

Authors: Niloufar Shafiei

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

Abstract
We present a new non-blocking doubly-linked list implementation for an asynchronous shared-memory system. It is the first such implementation for which an upper bound on amortized time complexity has been proved. In our implementation, operations access the list via cursors. Each cursor is located at an item in the list and is local to a process. In our implementation, cursors can be used to traverse and update the list, even as concurrent operations modify the list. The implementation supports two update operations, insertBefore and delete, and two move operations, moveRight and moveLeft. An insertBefore(c, x) operation inserts an item x into the list immediately before the cursor c's location. A delete(c) operation removes the item at the cursor c's location and sets the cursor to the next item in the list. The move operations move the cursor one position to the right or left. Update operations use single-word Compare&Swap instructions. Move operations only read shared memory and never change the state of the data structure. If all update operations modify different parts of the list, they run completely concurrently. A cursor is active if it is initialized, but not yet removed from the process's set of cursors. Let c.(op) be the maximum number of active cursors at any one time during the operation op. The amortized step complexity is O(c.(op)) for each update op and O(1) for each move. We provide a detailed correctness proof and amortized analysis of our implementation.
Cite as

Niloufar Shafiei. Non-Blocking Doubly-Linked Lists with Good Amortized Complexity. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 35:1-35:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{shafiei:LIPIcs.OPODIS.2015.35,
  author =	{Shafiei, Niloufar},
  title =	{{Non-Blocking Doubly-Linked Lists with Good Amortized Complexity}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{35:1--35: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.35},
  URN =		{urn:nbn:de:0030-drops-66787},
  doi =		{10.4230/LIPIcs.OPODIS.2015.35},
  annote =	{Keywords: non-blocking data structure, doubly-linked list, shared memory, amortized complexity, cursor}
}
  • Refine by Author
  • 1 Shafiei, Niloufar

  • Refine by Classification

  • Refine by Keyword
  • 1 amortized complexity
  • 1 cursor
  • 1 doubly-linked list
  • 1 non-blocking data structure
  • 1 shared memory

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

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