Amortized Lower Bounds for Shared Memory Data Types

Wednesday, April 17, 2019 - 3:00pm to 3:30pm

Event Calendar Category

LIDS & Stats Tea

Speaker Name

Siddhartha Jayanti



Building and Room Number

LIDS Lounge


As data sets become larger, there is an increasing need to develop parallel algorithms. For this reason, there has been a new burst of interest in efficient data structures designed for asynchronous shared-memory multiprocessors. In this model, the relative speeds of the processors can be arbitrary---in fact adversarial---thus, designing even a correct algorithm can be difficult. Classical algorithms have thus been inefficient---with polynomial overheads in the number of processes. However, recent results have shown the possibility of cutting these overheads down exponentially to only logarithmic, giving rise to the question of how small they can be made and whether they can be eliminated entirely. 

In this talk, I will present a novel general-technique for proving lower bounds for many different shared memory data types. In particular, our method obtains an optimal amortized lower bound for shared-memory counter objects and result in an Omega(m loglog (np/m)) step complexity lower bound for the shared-memory Union-Find data structure (the best known upper bound is O(m log(np/m))). To my knowledge, this is the only non-trivial lower bound known for the shared memory union-find problem. The result is joint work with Enric Boix, who is also a PhD student at MIT.


Siddhartha Jayanti is a PhD student of Professor Costis Daskalakis in the Computer Science and Artificial Intelligence Lab (CSAIL) at MIT. His research focuses on Statistics and Machine Learning. He got his Bachelor of Science in Engineering degree from Princeton University, where his undergraduate thesis was advised by Professor Robert Tarjan.

As an undergraduate, Siddhartha was a recipient of the Barry Goldwater Scholarship. His undergraduate research was funded in part by a Channels Scholarship from NSF's Center for Science of Information. His undergraduate thesis on shared-memory algorithms for the Concurrent Disjoint Set Union data structure received the Outstanding Computer Science Senior Thesis Prize from the Princeton CS department, The Calvin Dodd Maccracken Senior Thesis/Project Award from Princeton's School of Engineering and Applied Sciences, and was Runner-Up for CRA's Outstanding Undergraduate Research Award. Siddhartha was offered the NSF Graduate Research Fellowship and is currently funded by a National Defense Science and Engineering Graduate Fellowship.