Lower bounds on the amortized time complexity of shared objects

DOI10.1007/S00224-024-10184-WMaRDI QIDQ6635702

Arie Fouren, Hagit Attiya, Jeremy Ko

Publication date: 12 November 2024

Published in: Theory of Computing Systems (Search for Journal in Brave)

zbMATH Keywords

treesremote memory referenceslistsstacks and queuesstep complexitymonotone objects

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Computer system organization (68Mxx) Theory of data (68Pxx)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A time complexity lower bound for adaptive mutual exclusion
• Concurrency of operations on B-trees
• Concurrent disjoint set union
• Eine Extremalaufgabe aus der Graphentheorie.
• The amortized complexity of non-blocking binary search trees
• Efficient and practical constructions of LL/SC variables
• Shared-memory mutual exclusion: major research trends since 1986
• Universal constructions for multi-object operations
• Lock-free linked lists using compare-and-swap
• Practical implementations of non-blocking synchronization primitives
• On the inherent weakness of conditional synchronization primitives
• A Wait-free Queue with Polylogarithmic Step Complexity
• Ll/SC and atomic copy: constant time, space efficient implementations using only pointer-width CAS

This page was built for publication: Lower bounds on the amortized time complexity of shared objects

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6635702)