Lower bounds on the amortized time complexity of shared objects

DOI10.1007/S00224-024-10184-WMaRDI QIDQ6635702zbMATH OpenFDO

Authors Hagit Attiya, Arie Fouren, Jeremy Ko

Publication date 12 November 2024

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

Full work available at URL https://doi.org/10.1007/S00224-024-10184-W

zbMATH Keywords

listsmonotone objectsremote memory referencesstacks and queuesstep complexitytrees

Mathematics Subject Classification ID

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

Cites work

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

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)