This book discusses the recent research work on designing efficient fault-tolerant synchronization mechanisms for concurrent processes using the relatively new persistent memory technology that combines the low latency benefits of DRAM with the persistence of magnetic disks. The authors include all of the major contributions published to date, and also convey some perspective regarding how the problem itself is evolving. The results are described at a high level to enable readers to gain a quick and thorough understanding of the RME problem and its nuances, as well as various solutions that have been designed to solve the problem under a variety of important conditions and how they compare to each other.
Author(s): Sahil Dhoked, Wojciech Golab, Neeraj Mittal
Series: Synthesis Lectures on Distributed Computing Theory
Publisher: Springer
Year: 2023
Language: English
Pages: 131
City: Cham
Preface
Acknowledgments
Contents
About the Authors
1 Introduction
[DELETE]
References
2 Persistent Memory
[DELETE]
References
3 Prior Work
[DELETE]
References
4 Problem Formulation
[DELETE]
4.1 Modeling Steps and Execution Histories
4.2 Control Flow
4.3 Correctness Properties
4.4 Alternative Definitions of Correctness Properties
4.4.1 Starvation Freedom
4.5 Alternative Problem Definitions
4.6 Remote Memory References
4.7 Synchronization Primitives
References
5 Load and Store Based Algorithms
[DELETE]
5.1 Algorithm for Two-of-n-Processes
5.2 Adding Bounded Critical Section Reentry
5.3 An Algorithm for n Processes
References
6 Sublogarithmic Algorithms
6.1 Golab and Hendler's Algorithm
6.2 Jayanti, Jayanti and Joshi's Algorithm
6.2.1 Signal Object
6.2.2 Modified MCS Lock
6.2.3 Repair Procedure
6.2.4 Formal Description
6.3 Putting It All Together
References
7 Adaptive Algorithms
[DELETE]
7.1 Classification of RME Algorithms
7.2 Adding Recoverability
7.3 Adding Boundedness
7.4 Weak Recoverability
7.5 An Optimal Weakly Recoverable Lock
7.6 A Strongly Recoverable
7.6.1 A
7.6.2 A Well-Bounded Super-Adaptive RME Algorithm
7.7 Relation Between with CI-FCFS and k-FCFS
References
8 Constant Amortized Complexity Algorithm
[DELETE]
8.1 The Main Idea
8.1.1 Advancing the Token
8.2 Formal Description
8.3 Discussion
References
9 Abortable Recoverable Mutual Exclusion
[DELETE]
9.1 Problem Definition
9.1.1 Control Flow
9.1.2 Correctness Properties
9.2 Jayanti and Joshi's Algorithm
9.2.1 A Recoverable Min-Array
9.2.2 Abortable RME
9.3 Katzan and Morrison's Algorithm
9.3.1 A Δ-Ported Abortable Recoverable Lock
9.3.2 Tournament Tree
References
10 Tight Lower Bound
[DELETE]
References
11 System Wide Failures
[DELETE]
11.1 Barriers
11.1.1 Barrier Variation 1: Known Leader
11.1.2 Barrier Variation 2: Unknown Leader
11.2 Adding Recoverability
11.3 Adding Critical Section Reentry
11.4 Adding Failure Robust Fairness
References
12 Discussion and Open Problems
[DELETE]
References
