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 large-scale distributed systems. 
My interests include algorithms, data structures, and optimization. You can find some of my recent projects below.
Click here to see my 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.

Lease/Release: Architectural Support for Scaling Contended Data Structures
with Syed Kamran Haider
In PPoPP 2016, to appear.
[preliminary version]

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

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

Concurrent Data Structures and Tools

This project includes a growing library of data structures and tools, whose overall goal is scalable computation. 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.
[PDF] [code]

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]

Inherent Limitations of Hybrid Transactional Memory
with Justin Kopinsky, Petr Kuznetsov, Srivatsan Ravi, and Nir Shavit.
In DISC 2015.

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

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


Optimization in Data Centres

In my work at MSR, I often come across interesting optimization problems arising in practical contexts. These problems are often worst-case intractable, and must be solved under tight budget and time constraints in practice. The papers below describe some of our experience in tackling such problems.

Streaming Min-Max Hypergraph Partitioning
with Jennifer Iglesias and Milan Vojnovic.
In NIPS 2015.

A High-Radix, Low-Latency Optical Switch for Data Centres
with Hitesh Ballani, Paolo Costa, Adam Funnell, Joshua Benjamin, Philip Watts, and Benn Thomsen
Demo presented at the ACM Conference on Data Communication (SIGCOMM 2015).

Distributed 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. 

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

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.

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

Molecular Computation

Recently, there's been a lot of interest into distributed computation which occurs at the level of simple networks of finite-state agents, 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.

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























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