University of Paris Seminar Series on Data Analytics
in collaboration with the diNo group

Invited Seminar Talk

Fault-Tolerant Data Structures in Settings with Non-Volatile Main Memory
Prof Panagiota Fatourou, Universite Paris Cite (France), FORTH (Greece)

when: 24 March 2022, 2pm
where: online (email the organizer for connection details)


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. Another technique we will present addresses 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 the 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. 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, Canada. Her research interests focus on the principles of 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.

Hosted by: Themis Palpanas

List of past seminars