Constant-RMR implementations of CAS and other synchronization primitives using read and write operations

DOI10.1145/1281100.1281105MaRDI QIDQ5401387zbMATH OpenOpenAlexFDO

Authors Wojciech Golab, Vassos Hadzilacos, Danny Hendler, Philipp Woelfel

Publication date 13 March 2014

Published in Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/1807/26182

zbMATH Keywords

consensusshared memorymutual exclusionremote memory referencescomparison primitives

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Distributed algorithms (68W15) Distributed systems (68M14) Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.) (68N19)

Recommendations

• RMR-efficient implementations of comparison primitives using read and write operations
• An \(O(1)\) RMRs leader election algorithm
• On the inherent weakness of conditional synchronization primitives
• Distributed Computing
• Constant RMR solutions to reader writer synchronization

Cited in

(9)

• An \(O(1)\) RMRs leader election algorithm
• Sublogarithmic test-and-set against a weak adversary
• A time complexity lower bound for adaptive mutual exclusion
• Closing the complexity gap between FCFS mutual exclusion and mutual exclusion
• Randomized mutual exclusion with sub-logarithmic RMR-complexity
• An almost tight RMR lower bound for abortable test-and-set
• Tight bounds for asynchronous renaming
• RMR-efficient implementations of comparison primitives using read and write operations
• Ll/SC and atomic copy: constant time, space efficient implementations using only pointer-width CAS

This page was built for publication: Constant-RMR implementations of CAS and other synchronization primitives using read and write operations

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