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.2017.16
URN: urn:nbn:de:0030-drops-86513
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8651/
Go to the corresponding LIPIcs Volume Portal

Attiya, Hagit ; Fouren, Arie

Lower Bounds on the Amortized Time Complexity of Shared Objects

pdf-format:
LIPIcs-OPODIS-2017-16.pdf (1 MB)

Abstract

The amortized step complexity of an implementation measures its performance as a whole, rather than the performance of individual operations. Specifically, the amortized step complexity of an implementation is the average number of steps performed by invoked operations, in the worst case, taken over all possible executions. The amortized step complexity of a wide range of known lock- free implementations for shared data structures, like stacks, queues, linked lists, doubly-linked lists and binary trees, includes an additive factor linear in the point contention—the number of processes simultaneously active in the execution.
This paper shows that an additive factor, linear in the point contention, is inherent in the amortized step complexity for lock-free implementations of many distributed data structures, including stacks, queues, heaps, linked lists and search trees.

BibTeX - Entry

@InProceedings{attiya_et_al:LIPIcs:2018:8651,
  author =	{Hagit Attiya and Arie Fouren},
  title =	{{Lower Bounds on the Amortized Time Complexity of Shared Objects}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{James Aspnes and Alysson Bessani and Pascal Felber and Jo{\~a}o Leit{\~a}o},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8651},
  URN =		{urn:nbn:de:0030-drops-86513},
  doi =		{10.4230/LIPIcs.OPODIS.2017.16},
  annote =	{Keywords: monotone objects, stacks and queues, trees, step complexity, remote memory references}
}

Keywords: monotone objects, stacks and queues, trees, step complexity, remote memory references
Collection: 21st International Conference on Principles of Distributed Systems (OPODIS 2017)
Issue Date: 2018
Date of publication: 28.03.2018

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