Document Open Access Logo

Recoverable, Abortable, and Adaptive Mutual Exclusion with Sublogarithmic RMR Complexity

Authors Daniel Katzan, Adam Morrison

PDF

File

Thumbnail PDF
PDF
LIPIcs.OPODIS.2020.15.pdf
  • Filesize: 0.53 MB
  • 16 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Shared memory algorithms
Keywords
  • Mutual exclusion
  • recovery
  • non-volatile memory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We present the first recoverable mutual exclusion (RME) algorithm that is simultaneously abortable, adaptive to point contention, and with sublogarithmic RMR complexity. Our algorithm has O(min(K,log_W N)) RMR passage complexity and O(F + min(K,log_W N)) RMR super-passage complexity, where K is the number of concurrent processes (point contention), W is the size (in bits) of registers, and F is the number of crashes in a super-passage. Under the standard assumption that W = Θ(log N), these bounds translate to worst-case O((log N)/(log log N)) passage complexity and O(F + (log N)/(log log N)) super-passage complexity. Our key building blocks are:  
- A D-process abortable RME algorithm, for D ≤ W, with O(1) passage complexity and O(1+F) super-passage complexity. We obtain this algorithm by using the Fetch-And-Add (FAA) primitive, unlike prior work on RME that uses Fetch-And-Store (FAS/SWAP).
- A generic transformation that transforms any abortable RME algorithm with passage complexity of B < W, into an abortable RME lock with passage complexity of O(min(K,B)).

Cite As Get BibTex

Daniel Katzan and Adam Morrison. Recoverable, Abortable, and Adaptive Mutual Exclusion with Sublogarithmic RMR Complexity. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.OPODIS.2020.15

Author Details

Daniel Katzan
  • Tel Aviv University, Israel
Adam Morrison
  • Tel Aviv University, Israel

Funding

Israel Science Foundation (grant No. 2005/17) and Blavatnik ICRC at TAU.

References

  1. Y. Afek, H. Attiya, A. Fouren, G. Stupp, and D. Touitou. Long-Lived Renaming Made Adaptive. In PODC, 1999. Google Scholar
  2. A. Alon and A. Morrison. Deterministic Abortable Mutual Exclusion with Sublogarithmic Adaptive RMR Complexity. In PODC, 2018. Google Scholar
  3. J.H. Anderson and Y.J. Kim. An Improved Lower Bound for the Time Complexity of Mutual Exclusion. Distributed Computing, 15(4), 2002. Google Scholar
  4. H. Attiya. Adapting to Point Contention with Long-Lived Safe Agreement. In SIROCCO, 2006. Google Scholar
  5. H. Attiya and A. Fouren. Algorithms Adapting to Point Contention. JACM, 50(4), 2003. Google Scholar
  6. H. Attiya, D. Hendler, and P. Woelfel. Tight RMR Lower Bounds for Mutual Exclusion and Other Problems. In STOC, 2008. Google Scholar
  7. D.Y.C. Chan and P. Woelfel. Recoverable Mutual Exclusion with Constant Amortized RMR Complexity from Standard Primitives. In PODC, 2020. Google Scholar
  8. T.S. Craig. Building FIFO and Priority-Queuing Spin Locks from Atomic Swap, 1993. Google Scholar
  9. S. Dhoked and N. Mittal. An Adaptive Approach to Recoverable Mutual Exclusion. In PODC, 2020. Google Scholar
  10. E.W. Dijkstra. Solution of a Problem in Concurrent Programming Control. CACM, 8(9), 1965. Google Scholar
  11. W. Golab and D. Hendler. Recoverable Mutual Exclusion in Sub-Logarithmic Time. In PODC, 2017. Google Scholar
  12. W. Golab and D. Hendler. Recoverable Mutual Exclusion Under System-Wide Failures. In PODC, 2018. Google Scholar
  13. W. Golab and A. Ramaraju. Recoverable Mutual Exclusion: [Extended Abstract]. In PODC, 2016. Google Scholar
  14. W. Golab and A. Ramaraju. Recoverable Mutual Exclusion. Distributed Computing, 32(6), 2019. Google Scholar
  15. P. Jayanti. F-Arrays: Implementation and Applications. In PODC, 2002. Google Scholar
  16. P. Jayanti. Adaptive and Efficient Abortable Mutual Exclusion. In PODC, 2003. Google Scholar
  17. P. Jayanti and S. Jayanti. Constant Amortized RMR Abortable Mutex for CC and DSM. In PODC, 2019. Google Scholar
  18. P. Jayanti, S. Jayanti, and A. Joshi. A Recoverable Mutex Algorithm with Sub-Logarithmic RMR on Both CC and DSM. In PODC, 2019. Google Scholar
  19. P. Jayanti, S.V. Jayanti, and A. Joshi. Optimal Recoverable Mutual Exclusion Using only FASAS. In NETYS, 2018. Google Scholar
  20. P. Jayanti and A. Joshi. Recoverable FCFS Mutual Exclusion with Wait-Free Recovery. In DISC, 2017. Google Scholar
  21. P. Jayanti and A. Joshi. Recoverable Mutual Exclusion with Abortability. In NETYS, 2019. Google Scholar
  22. Daniel Katzan and Adam Morrison. Recoverable, Abortable, and Adaptive Mutual Exclusion with Sublogarithmic RMR Complexity. CoRR, 2020. URL: http://arxiv.org/abs/2011.07622.
  23. J.M. Mellor-Crummey and M.L. Scott. Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors. TOCS, 9(1), 1991. Google Scholar
  24. M. M. Michael. Hazard pointers: safe memory reclamation for lock-free objects. TPDS, 15(6), 2004. Google Scholar
  25. M.L. Scott. Non-blocking Timeout in Scalable Queue-based Spin Locks. In PODC, 2002. Google Scholar
  26. M.L. Scott and W.N. Scherer. Scalable Queue-based Spin Locks with Timeout. In PPoPP, 2001. Google Scholar
  27. Gadi Taubenfeld. Synchronization algorithms and concurrent programming. Pearson / Prentice Hall, 2006. Google Scholar
  28. J.H. Yang and J.H. Anderson. A fast, scalable mutual exclusion algorithm. Distributed Computing, 9(1), 1995. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact