Laws of order, expensive synchronization in concurrent algorithms cannot be eliminated

DOI10.1145/1926385.1926442MaRDI QIDQ5408568zbMATH OpenOpenAlexFDO

Authors Hagit Attiya, Danny Hendler, Petr Kuznetsov, Maged M. Michael, Martin Vechev, Rachid Guerraoui

Publication date 10 April 2014

Published in Proceedings of the 38th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages (Search for Journal in Brave)

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

zbMATH Keywords

algorithmslower boundsconcurrencymemory barriersmemory fences

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Parallel algorithms in computer science (68W10) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Synchronizing without locks is inherently expensive
• On the inherent weakness of conditional synchronization primitives
• Comprehensive synchronization elimination for Java.
• Highly-efficient wait-free synchronization

Cited in

(6)

• Scheduling computations with provably low synchronization overheads
• Sublogarithmic test-and-set against a weak adversary
• Process-commutative distributed objects: from cryptocurrencies to Byzantine-fault-tolerant CRDTs
• Relaxed data types as consistency conditions
• Set-linearizable implementations from read/write operations: sets, fetch \& increment, stacks and queues with multiplicity
• Lower bounds on message passing implementations of multiplicity-relaxed queues and stacks

This page was built for publication: Laws of order, expensive synchronization in concurrent algorithms cannot be eliminated

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