Asynchronous Concurrency in Data Structures | Richard M. Karp Distinguished Lecture

This talk will explore the question of whether and by how much operations on data structures can be sped up by using multiple unsynchronized processes. Taking advantage of concurrency in this setting is a challenge. The talk will describe work by Siddhartha Jayanti and Robert E. Tarjan on the efficiency of concurrent disjoint set union algorithms, including recent unpublished work that uses new ideas to eliminate the need for randomization.