Seminars at the Faculty of Informatics

Data Structures of the Future: Concurrent, Optimistic, and Relaxed


Dan Alistarh


IST, Austria


Tuesday, April 4, 2017


USI Lugano Campus, room SI-003, informatics building (Via G. Buffi 13)






A central computing trend over the last decade has been the need to process increasingly larger amounts of data as efficiently as possible.This development is challenging both software and hardware design, and is altering the way data structures and algorithms are constructed, implemented, and deployed.

In this talk, I will present some examples of such new data structure design ideas and implementations. In particular, I will discuss some inherent limitations of parallelizing classic data structures, and then focus on approaches to circumvent these limitations. The first approach is to relax the algorithm semantics, to allow for approximation,
randomization, or both. The second is to modify the underlying hardware architecture to unlock more parallelism. Time permitting, I will also cover results showing that both approaches can improve real-world performance, and touch upon some of the major open questions in the area.




Dan Alistarh is an Assistant Professor at IST Austria, currently visiting ETH Zurich on an SNF Ambizione Fellowship. Previously, he was a Researcher at Microsoft Research, Cambridge, UK, and a Postdoctoral Associate at MIT CSAIL. He received his PhD from the EPFL, under the guidance of Prof. Rachid Guerraoui. 
His research focuses on distributed algorithms and concurrent data structures, and spans from algorithms and lower bounds, to practical implementations.




Prof. Fernando Pedoone