 |
Paris Descartes University Seminar Series on Data Analytics Invited Seminar Talk |
 |
|
Prof Panagiota Fatourou, University of Crete & FORTH ICS (Greece) when: 20 June 2019, 2pm where: room Turing Conseil, 7th floor, Paris Descartes University, 45 Rue Des Saints Peres, Paris 75006 Abstract 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. These implementations are linearizable and tolerate any number of crash failures. Insert and Delete operations that modify different parts of the tree do not interfere with one another, so they can run completely concurrently. The implementations work in a dynamic system where the number of processes may change over time. Experiments illustrate the good performance and scalability properties of the implementations. Short Bio Panagiota Fatourou is an Associate Professor of Computer Science at the University of Crete and at the Foundation of Research and Technology-Hellas (FORTH ICS), Greece. She has worked as a visiting Professor at EPFL in Switzerland, as a full-time faculty member at the University of Ioannina in Greece, and as a postdoc researcher at Max-Planck Institut fuer Informatik in Germany and at the University of Toronto in Canada. She is an elected member of the ACM Europe Council (currently serving as the treasurer) and an ACM Distinguished Speaker. She has served as the editor of the Distributed Computing Column of the Bulletin of EATCS, as the General Chair of ACM PODC 2013, as the PC chair of OPODIS 2016 and SSS 2017 (distributed computing track), and as a member of the steering committees of PODC and OPODIS. She has participated in the PC of more than 35 conferences. She has been the coordinator of a Marie-Curie Initial Training Network and she has participated in many additional research and development projects mostly funded by the European Commission. Her research interests focus on the theory of Parallel and Distributed Computing. Hosted by: Themis Palpanas List of past seminars |