DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2017.16

Lower Bounds on the Amortized Time Complexity of Shared Objects

Authors: Hagit Attiya and Arie Fouren

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

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.

Cite as

Hagit Attiya and Arie Fouren. Lower Bounds on the Amortized Time Complexity of Shared Objects. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{attiya_et_al:LIPIcs.OPODIS.2017.16,
  author =	{Attiya, Hagit and Fouren, Arie},
  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 =	{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.16},
  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}
}

Document

DOI: 10.4230/LIPIcs.OPODIS.2015.36

Poly-Logarithmic Adaptive Algorithms Require Unconditional Primitives

Authors: Hagit Attiya and Arie Fouren

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

Abstract

This paper studies the step complexity of adaptive algorithms using primitives stronger than reads and writes. We first consider unconditional primitives, like fetch&inc, which modify the value of the register to which they are applied, regardless of its current value. Unconditional primitives admit snapshot algorithms with O(log(k)) step complexity, where k is the total or the point contention. These algorithms combine a renaming algorithm with a mechanism for propagating values so they can be quickly collected. When only conditional primitives, e.g., compare&swap or LL/SC, are used (in addition to reads and writes), we show that any collect algorithm must perform Omega(k) steps, in an execution with total contention k in O(log(log(n))). The lower bound applies for snapshot and renaming, both one-shot and long-lived. Note that there are snapshot algorithms whose step complexity is polylogarithmic in n using only reads and writes, but there are no adaptive algorithms whose step complexity is polylogarithmic in the contention, even when compare&swap and LL/SC are used.

Cite as

Hagit Attiya and Arie Fouren. Poly-Logarithmic Adaptive Algorithms Require Unconditional Primitives. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{attiya_et_al:LIPIcs.OPODIS.2015.36,
  author =	{Attiya, Hagit and Fouren, Arie},
  title =	{{Poly-Logarithmic Adaptive Algorithms Require Unconditional Primitives}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{36:1--36:16},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.36},
  URN =		{urn:nbn:de:0030-drops-66793},
  doi =		{10.4230/LIPIcs.OPODIS.2015.36},
  annote =	{Keywords: collect, atomic snapshot, renaming, fetch\&inc, compare\&swap}
}

Search Results

Documents authored by Fouren, Arie

Lower Bounds on the Amortized Time Complexity of Shared Objects

Abstract

Cite as

Poly-Logarithmic Adaptive Algorithms Require Unconditional Primitives

Abstract

Cite as

Thanks for your feedback!

Could not send message