Amortized Lower Bounds for Shared Memory Data Types

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.