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

DOI10.1145/1926385.1926442zbMATH Open1284.68423OpenAlexW4244624509MaRDI QIDQ5408568FDOQ5408568

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

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

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)

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)