Department of Computer, Control and Management Engineering

Concurrent dictionaries lie in the heart of most modern concurrent applications. We present NB-BST, the first implementation of a non-blocking binary search tree in an asynchronous shared-memory system using single-word compare-and-swap. We also built upon NB-BST to get PNB-BST, the first implementation of a search tree data structure in an asynchronous shared-memory system that provides a wait-free algorithm for executing complex queries (such as range queries) on the tree, in addition to non-blocking algorithms for Insert, Delete and Find.  Such queries are required in many big-data applications, where shared in-memory tree-based data indices must be created for fast data retrieval and useful data analytics. We further touch upon other wait-free implementations of dictionaries and present techniques for achieving efficient synchronization.

Short Bio

Panagiota Fatourou is an Associate 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 has been a visiting Professor at the School of Computer and Communication Sciences, École Polytechnique Fédérale de Lausanne in Switzerland. Prior to joining the University of Crete and FORTH ICS, she was a full-time faculty member at the Department of Computer Science & Engineering of the University of Ioannina. 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 theory of parallel and distributed computing.

Panagiota Fatourou is the chair of the ACM Europe Council. 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 is a member-at-large of the steering committee of the ACM Symposium on Principles of Distributed Computing (PODC) and she has served in the steering committee of the International Conference on Principles of Distributed Systems (OPODIS). She has participated in the PC of more than 35 conferences. She has been an ACM Distinguished Speaker.