Document Open Access Logo

Lower Bounds on the Amortized Time Complexity of Shared Objects

Authors Hagit Attiya, Arie Fouren

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2017.16.pdf
  • Filesize: 1.31 MB
  • 18 pages

Document Identifiers

Author Details

Hagit Attiya
Arie Fouren

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.OPODIS.2017.16

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.

Subject Classification

Keywords
  • monotone objects
  • stacks and queues
  • trees
  • step complexity
  • remote memory references

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. James H Anderson, Yong-Jik Kim, and Ted Herman. Shared-memory mutual exclusion: major research trends since 1986. Distributed Computing, 16(2):75-110, 2003. Google Scholar
  2. Richard J. Anderson and Heather Woll. Wait-free parallel algorithms for the union-find problem. In Proceedings of the Twenty-third Annual ACM Symposium on Theory of Computing, STOC '91, pages 370-380, New York, NY, USA, 1991. ACM. URL: http://dx.doi.org/10.1145/103418.103458.
  3. Hagit Attiya and Arie Fouren. Poly-logarithmic adaptive algorithms require revealing primitives. Journal of Parallel and Distributed Computing, 109:102-116, 2017. URL: http://dx.doi.org/10.1016/j.jpdc.2017.05.010.
  4. Rudolf Bayer and Mario Schkolnick. Concurrency of operations on b-trees. Acta informatica, 9(1):1-21, 1977. Google Scholar
  5. Faith Ellen, Panagiota Fatourou, Joanna Helga, and Eric Ruppert. The amortized complexity of non-blocking binary search trees. In Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, PODC '14, pages 332-340, New York, NY, USA, 2014. ACM. URL: http://dx.doi.org/10.1145/2611462.2611486.
  6. Mikhail Fomitchev and Eric Ruppert. Lock-free linked lists and skip lists. In Proceedings of the Twenty-third Annual ACM Symposium on Principles of Distributed Computing, PODC '04, pages 50-59, New York, NY, USA, 2004. ACM. URL: http://dx.doi.org/10.1145/1011767.1011776.
  7. Timothy Harris. A pragmatic implementation of non-blocking linked-lists. Distributed Computing, pages 300-314, 2001. Google Scholar
  8. Steve Heller, Maurice Herlihy, Victor Luchangco, Mark Moir, William N Scherer, and Nir Shavit. A lazy concurrent list-based set algorithm. In Proceedings of the 9th international conference on Principles of Distributed Systems, pages 3-16. Springer-Verlag, 2005. Google Scholar
  9. Maurice Herlihy and Nir Shavit. The art of multiprocessor programming. Morgan Kaufmann, 2011. Google Scholar
  10. Yong-Jik Kim and James H Anderson. A time complexity lower bound for adaptive mutual exclusion. Distributed Computing, 24(6):271-297, 2012. Google Scholar
  11. Maged M Michael. High performance dynamic lock-free hash tables and list-based sets. In Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, pages 73-82. ACM, 2002. Google Scholar
  12. Eric Ruppert. Analysing the average time complexity of lock-free data structures. In Workshop on Complexity and Analysis of Distributed Algorithms, 2016. [http://www.birs.ca/events/2016/5-day-workshops/16w5152/videos/watch/201612011630-Ruppert.html; accessed 22-Mar-2017].
  13. Niloufar Shafiei. Non-Blocking Data Structures Handling Multiple Changes Atomically. PhD thesis, York University, 2015. Google Scholar
  14. R. Kent Treiber. Systems programming: Coping with parallelism. International Business Machines Incorporated, Thomas J. Watson Research Center, 1986. Google Scholar
  15. P. Turan. On an extremal problem in graph theory (in Hungarian). Mat. Fiz. Lapok, 48:436-452, 1941. Google Scholar
  16. John D Valois. Lock-free linked lists using compare-and-swap. In Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, pages 214-222. ACM, 1995. Google Scholar
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 About DROPS Imprint Privacy Contact