Upper and Lower Bounds on the Space Complexity of Detectable Objects
Ohad Ben-Baruch, Danny Hendler, Matan Rusanovsky · 2020
The emergence of systems with non-volatile main memory (NVM) increases the interest in the design of recoverable concurrent objects that are robust to crash-failures, since their operations are able to recover from such failures by using state retained in NVM. Of particular interest are recoverable algorithms that, in addition to ensuring object consistency, also provide detectability, a correctness condition requiring that the recovery code can infer if the failed operation was linearized or not and, in the former case, obtain its response.