OPODIS 2022

Recoverable Computing

Non-Volatile Memory (NVM) is an emerging memory technology which aims to address the high computational demands of modern applications and support recovery from crashes. Recovery ensures that after a crash every executed operation is able to recover and return a correct response.

This talk will shed light on different aspects of the question "How does concurrent computing change in systems with NVM and what will the impact of persistent memory be on the way we compute?". Specifically, the talk will touch upon the following four main challenges in NVM computing:

• Challenge 1: How to appropriately model and abstract fundamental aspects of NVM computing? The talk will provide an overview of the theoretical framework for NVM computing, including a discussion of correctness conditions, progress guarantees, failure types, etc.
• Challenge 2: How to compute in a recoverable way at no significant cost? The talk will summarize state-of-the-art generic approaches for deriving recoverable synchronization algorithms, as well as recoverable implementations of many widely-used concurrent data structures on top of them. The collection of data structures includes fundamental structures, such as stacks and queues, but also more complex structures that implement sets, such as linked-lists and trees.
• Challenge 3: How to analyze the cost of recoverable algorithms? The talk will present a way of analyzing the cost of persistence instructions, not by simply counting them but by separating them into categories based on the impact they have on the performance. This analysis reveals that understanding the actual persistence cost of an algorithm in machines with NVM, is more complicated than previously thought, and requires a thorough evaluation, since the performance impact of different persistence instructions may greatly vary.
• Challenge 4: When is Recoverable Consensus Harder Than Consensus? The talk will briefly discuss the ability of different shared object types to solve recoverable consensus using NVM when processes crash and recover, and it will compare the difficulty of solving recoverable consensus to the difficulty of solving the standard consensus problem in a system with halting failures.

For each of the above challenges, the talk will present main results, provide some of the details of the best-performing techniques, and discuss open problems and directions for further research. Some of the results that will be discussed in detail have appeared in recent papers in PPoPP 2022 (1/2), PPoPP 2022 (2/2), and PODC 2022.

Panagiota Fatourou is a Professor at the University of Crete and the Foundation for Research and Technology - Hellas (FORTH). She has worked as a Marie-Curie Individual Fellow at Université Paris Cité, two times as a visiting Professor at École Polytechnique Fédérale de Lausanne (EPFL), and as a visiting researcher at the University of York and the University of Toronto. She has been a postdoc at Max-Planck Institut für Informatik and at the University of Toronto, and as a visiting postdoc at the University of Brown. Her research interests focus on parallel and distributed computing.

P. Fatourou has served as the chair of the ACM Europe Council (October 2019 – June 2021). Since July 2015, she is an elected member of the Council, currently serving as the Past Chair. She has served as the editor of the Distributed Computing Column of the Bulletin of the European Association for Theoretical Computer Science (BEATCS), and as the General Chair of the ACM Symposium on Principles of Distributed Computing (PODC 2013). She has also served as a member-at-large of the steering committees of PODC and OPODIS. She has been the PC co-Chair of the 20th International Conference on Principles of Distributed Systems (OPODIS 2016), and of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2017). She has served as an ACM Distinguished Speaker and a Featured ACM Member.