Improved implementations of binary universal operations

DOI10.1145/502102.502105MaRDI QIDQ3196625zbMATH OpenOpenAlexFDO

Authors Hagit Attiya, Eyal Dagan

Publication date 30 October 2015

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/502102.502105

zbMATH Keywords

asynchronous shared-memory systemscontention-sensitive algorithmsdeterministic coin tossingload-linked/store-conditional operationsuniversal operationswait-free algorithms

Mathematics Subject Classification ID

Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Efficient and practical constructions of LL/SC variables
• On the inherent weakness of conditional primitives
• Distributed Computing – IWDC 2005
• On the uncontended complexity of consensus
• Pragmatic primitives for non-blocking data structures

Cited in

(7)

• Bounded-wait combining: constructing robust and high-throughput shared objects
• Built-in coloring for highly-concurrent doubly-linked lists
• Universal constructions that ensure disjoint-access parallelism and wait-freedom
• Highly concurrent multi-word synchronization
• Ll/SC and atomic copy: constant time, space efficient implementations using only pointer-width CAS
• Faster randomized repeated choice and DCAS
• Fast and fair randomized wait-free locks

This page was built for publication: Improved implementations of binary universal operations

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