【ERC Coffee House】Fault-Tolerant Data Structures in Settings with Non-Volatile Main Memory [Panagiota Fatourou]

Date

Thursday 22nd September @ 09:30 – 11:00 (UK time)

Presenter

Prof. Panagiota Fatourou

Affiliation

FORTH and University of Crete

Location

[Online]
Meeting link: https://welink.zhumu.com/j/100950586

Note: this is a talk open to the public.

Abstract

This talk will present generic approaches for deriving recoverable synchronization algorithms, as well as recoverable implementations of many widely-used concurrent data structures on top of them. Such implementations are appealing for emerging systems featuring byte-addressable non-volatile main memory (NVMM), whose persistence allows to efficiently resurrect failed processes after crashes. Recovery ensures that after a crash, every executed operation is able to recover and return a correct response, and that the state of the data structure is not corrupted.

Our experimental analysis reveals the performance power of employing software combining for achieving recoverable synchronization and for designing highly-efficient fundamental recoverable data structures, such as stacks and queues. We also address more complex data structures, such as linked-lists, and tree-like structures that implement sets. Our experimental analysis introduces a new 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 performance. The analysis reveals that understanding the actual persistence cost of an algorithm in machines with real NVMM, is more complicated than previously thought, and requires a thorough evaluation, since the impact of different persistence instructions on performance may greatly vary.

Short Bio

Panagiota Fatourou is a Professor at the Department of Computer Science of the University of Crete, Greece, and the Institute of Computer Science (ICS) of the Foundation for Research and Technology – Hellas (FORTH). She is currently working at the University of Paris, LIPADE, as a Marie-Curie Individual Fellow (October 2021 – September 2022). She has repeatedly worked as a visiting Professor at the School of Computer and Communication Sciences, École Polytechnique Fédérale de Lausanne in Switzerland, and as a visiting researcher at the University of York and the University of Toronto in Canada. She has worked as a postdoc at Max-Planck Institut für Informatik, Saarbrücken, Germany, and at the Computer Science Department of the University of Toronto. She has been a visiting postdoc at the University of Brown. Her research interests focus on parallel and distributed computing. Panagiota 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.