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

randomizationshared memorydining philosophersmulti-word locking

Mathematics Subject Classification ID

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

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)

• Highly-Concurrent Multi-word Synchronization
• Highly concurrent multi-word synchronization
• Built-in coloring for highly-concurrent doubly-linked lists
• Lock-free algorithms under stochastic schedulers
• 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)