Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Dan Alistarh

I’m a Researcher at Microsoft Research Cambridge, and the Morgan Fellow at Downing College, University of Cambridge.
Before coming to MSR, I spent a year as an SNF PostDoc at MIT CSAIL, where I've had the pleasure to work with professors Nir Shavit and Nancy Lynch. I received my PhD in Computer Science at the EPFL, under the brilliant guidance of Prof. Rachid Guerraoui.

My research is on the theory and practice of synchronization in large-scale distributed systems. 
My interests include concurrent data structures, distributed algorithms, and optimization for large-scale data analytics. You can find some of my recent projects below.
Click here to see the complete publication list, and here for drafts and working papers.

Optimistic Concurrency

Optimistic programming patterns (a.k.a. non-blocking or lock-free) are a popular way of building concurrent algorithms based on the idea that, within any bounded period of time, at least one of the pending operations should complete. This project explores the behavior of these optimistic algorithms in realistic worst-case scenarios, which is usually high concurrency.

Non-Blocking Algorithms under Stochastic Schedulers
with Thomas Sauerwald and Milan Vojnovic
In PODC 2015.
[preliminary version]

Are Lock-Free Concurrent Algorithms Practically Wait-Free?
with Keren Censor-Hillel and Nir Shavit
In STOC 2014.
[PDF] [MITNews Coverage]  [CACM Coverage]

Fast Concurrent Data Structures

This project includes a growing library of data structures and tools, whose main goal is to scale computation to very high thread counts. This often entails combining a wide range of ideas, from randomized algorithmic techniques to operating system and hardware support.

ThreadScan: Automatic and Scalable Memory Reclamation
with William Leiserson, Alexander Matveev, and Nir Shavit
In SPAA 2015.
[coming soon]

The SprayList: A Scalable Relaxed Priority Queue
with Justin Kopinsky, Jerry Li, and Nir Shavit. 
In PPoPP 2015. (Winner of Best Artefact Award.)
[preliminary version] [code] [Slashdot Coverage]

The LevelArray: A Fast, Practical Long-Lived Renaming Algorithm
with Justin Kopinsky, Alexander Matveev, and Nir Shavit.
In ICDCS 2014.
[PDF]

StackTrack: An Automated Transactional Approach to Concurrent Memory Reclamation
with Patrick Eugster, Maurice Herlihy, Alexander Matveev, and Nir Shavit.
In EuroSys 2014.
[PDF] [code]

The Power of Message-Passing

Distributed computation is often split into shared-memory and message-passing, based on the communication primitives employed. This line of work looks at how we can leverage message-passing to speed up key distributed tasks, such as agreement or task allocation. 
 

How to Elect a Leader Faster than a Tournament
with Rati Gelashvili and Adrian Vladu.
In PODC 2015.
[PDF]

Balls-into-Leaves: Sub-logarithmic Renaming in Synchronous Message-Passing Systems
with Oksana Denysyuk, Luis Rodrigues and Nir Shavit.
In PODC 2014.
Invited to the Special Issue of Distributed Computing dedicated to PODC 2014.
[PDF]

Communication-Efficient Randomized Consensus
with James Aspnes, Valerie King and Jared Saia.
In DISC 2014.
[PDF]

Molecular Computation

Recently, there's been a lot of interest into distributed computation which occurs at the level of networks of finite-state agents, interacting randomly, and updating their state using simple rules. Such systems are generally known as population protocols. In this project, we look at efficient algorithms for solving fundamental tasks in such networks.

Polylogarithmic-Time Leader Election in Population Protocols
with Rati Gelashvili.
In ICALP 2015.
[PDF]

Fast and Exact Majority in Population Protocols
with Rati Gelashvili and Milan Vojnovic.
In PODC 2015.
[PDF]

 

 

Microsoft Research Cambridge
21 Station Road
Cambridge CB1 2FB, UK
Email: dan.alistarh at microsoft dot com