Efficient multi-word locking using randomization

DOI10.1145/1073814.1073862MaRDI QIDQ5177246zbMATH OpenOpenAlexFDO

Authors Phuong Hoai Ha, Philippas Tsigas, Mirjam Wattenhofer, Roger Wattenhofer

Publication date 10 March 2015

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

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

zbMATH Keywords

dining philosophersmulti-word lockingrandomizationshared memory

Mathematics Subject Classification ID

Distributed systems (68M14) Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.) (68N19) Theory of operating systems (68N25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15) Randomized algorithms (68W20)

Recommendations

• Randomized mutual exclusion in \(\mathcal{O}(\log N / \log \log N)\) RMRs
• A fast, scalable mutual exclusion algorithm
• Randomized two-process wait-free test-and-set

Cited in

(5)

• Built-in coloring for highly-concurrent doubly-linked lists
• Lock-free algorithms under stochastic schedulers
• Highly-Concurrent Multi-word Synchronization
• Highly concurrent multi-word synchronization
• Efficient multi-word compare and swap

This page was built for publication: Efficient multi-word locking using randomization

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