Research

You can find some older research directions and publications below:

Analyzing Optimistic Concurrency

Optimistic concurrent algorithms (a.k.a. non-blocking or lock-free) are a popular class of concurrent algorithms based on the idea that the system as a whole should always make progress, even though individual threads may not. In this project, we examine their practical behaviour in conjunction with scheduling models and architectural support.

Are Lock-Free Concurrent Algorithms Practically Wait-Free?
with Keren Censor-Hillel and Nir Shavit.
In the 46th ACM Symposium on Theory of Computing (STOC 2014).
Full version accepted to Journal of the ACM.
[PDF]

Non-Blocking Algorithms under Stochastic Schedulers
with Thomas Sauerwald and Milan Vojnovic.
In the 34th ACM Symposium on Principles of Distributed Computing (PODC 2015).
[PDF]

Lease/Release: Architectural Support for Scaling Contended Data Structures
with William Hasenplaugh and Kamran Haider.
In Proceedings of the 2016 Symposium on Principles and Practice of Parallel Programming (PPoPP 2016).
Invited to Special Issue of Transactions on Parallel Computing dedicated to PPoPP 2016.
[PDF]

Concurrent Data Structures and Tools

This project consists of a growing library of scalable concurrent data structures, and related concurrency tools.

ThreadScan: Automatic and Scalable Memory Reclamation
with William Leiserson, Alexander Matveev, and Nir Shavit.
In the ACM Symposium on Algorithms and Architectures (SPAA 2015).
Invited to the Special Issue of Transactions on Parallel Computing dedicated to SPAA 2015.
[PDF]

The SprayList: A Scalable Relaxed Priority Queue
with Justin Kopinsky, Jerry Li, and Nir Shavit.
In the Symposium on Principles and Practice of Parallel Programming (PPoPP 2015).
Best Artefact Award.
[PDF]

Inherent Limitations of Hybrid Transactional Memory
with Justin Kopinsky, Petr Kuznetsov, Srivatsan Ravi, and Nir Shavit
In the 29th International Symposium on Distributed Computing (DISC 2015).
[PDF]

StackTrack: An Automated Transactional Approach to Concurrent Memory Reclamation
with Patrick Eugster, Maurice Herlihy, Alexander Matveev, and Nir Shavit.
In the 2014 European Conference on Computer Systems (EuroSys 2014).
[PDF]

The LevelArray: A Fast, Practical Long-Lived Renaming Algorithm
with Justin Kopinsky, Alexander Matveev, and Nir Shavit.
In the 34th International Conference on Distributed Computing Systems (ICDCS 2014).
[PDF]

Distributed Optimization

This project consists of solutions to optimization problems arising in practice, in particular where assignment decisions must be made in a distributed fashion. 

Streaming Min-Max Hypergraph Partitioning
with Jenny Iglesias and Milan Vojnovic.
In Neural Information Processing Systems (NIPS 2015).
[PDF]

A High-Radix, Low-Latency Optical Switch for Data Centers
with Hitesh Ballani, Paolo Costa, Adam Funnell, Joshua Benjamin, Philip Watts, and Benn Thomsen.
Demo presented at SIGCOMM 2015.
[PDF]

Molecular Computation

We look at the computational power and complexity characteristics of a model for computation by molecules called population protocols. Specifically, we are interested in the speed at which certain fundamental tasks, such as leader election and consensus, can be solved in this model, contrasted against the complexity of the interacting molecules. 

Time-Space Trade-offs in Population Protocols
with James Aspnes, David Eisenstat, Rati Gelashvili, and Ronald L. Rivest.
Preliminary version on arXiv.

Fast and Exact Majority in Population Protocols
with Rati Gelashvili and Milan Vojnovic.
In the 34th ACM Symposium on Principles of Distributed Computing (PODC 2015).
[PDF]

Polylogarithmic-Time Leader Election in Population Protocols
with Rati Gelashvili.
[PDF]
In the International Colloquium on Automata, Languages and Programming (ICALP 2015).