Abstract
Although crash failures do occur in the real world, they are rare in practice. As a result, we expect most of the super-passages to be failure-free. Thus it is desirable to design RME algorithms whose RMR complexity adapts to the number of recent failures in the system. Ideally, such an algorithm would incur only \({O}\left( 1\right) \) RMRs in any passage that is not 0-failure-concurrent. In this chapter, we discuss different notions of adaptiveness and describe several RME algorithms that can adapt to the number of recent failures in the system.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Sahil Dhoked and Neeraj Mittal. An adaptive approach to recoverable mutual exclusion. In Proc. of the 39th ACM Symposium on Principles of Distributed Computing (PODC), PODC ’20, pages 1–10, New York, NY, USA, 2020. Association for Computing Machinery.
Wojciech Golab and Aditya Ramaraju. Recoverable mutual exclusion. In Proc. of the 35th ACM Symposium on Principles of Distributed Computing (PODC), pages 65–74, 2016.
Wojciech Golab and Aditya Ramaraju. Recoverable mutual exclusion. Distributed Computing (DC), 32(6):535–564, 2019.
John M. Mellor-Crummey and Michael L. Scott. Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Transactions on Computer Systems (TOCS), 9(1):21–65, 1991.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this chapter
Cite this chapter
Dhoked, S., Golab, W., Mittal, N. (2023). Adaptive Algorithms. In: Recoverable Mutual Exclusion. Synthesis Lectures on Distributed Computing Theory. Springer, Cham. https://doi.org/10.1007/978-3-031-20002-1_7
Download citation
DOI: https://doi.org/10.1007/978-3-031-20002-1_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-20001-4
Online ISBN: 978-3-031-20002-1
eBook Packages: Synthesis Collection of Technology (R0)eBColl Synthesis Collection 12